Baekjoon2110: 공유기 설치

공유기 설치

2 초

128 MB

30853

11897

8441

39.544%

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

풀이

만족하는 값  중 최대값을 구하라 → Upper Bound를 구해야한다

N개의 위치값을 먼저 정렬하면 arr[0]~arr[N-1] 의 수가 정렬된다.

공유기 사이 거리의 최소값은 1부터 arr[N-1]-arr[0] 까지 가능하고

Upper Bound이므로 끝 값에 1을 더해준다. 즉, arr[N-1]-arr[0]+1이 최대값이다.

공유기 설치

최소값과 최대값을 통해 mid값을 구하고 이 거리값으로 공유기의 설치를 하나씩 하면서 몇 개를 설치할 수 있는지 구한다

설치할 수 있는 개수가 C보다 같거나 크면 공유기 사이의 거리가 이보다 넓어질 수 있다는 의미이다 → min=mid+1

C보다 작으면 거리를 좁혀서 더 많은 공유기를 설치해야한다는 뜻이다 →  max = mid 이다 (Upper Bound 식)

결과값

설치할 수 있는 개수가 C 보다 많아지는 최소의 길이가 구해진다 여기서 -1을 하는 순간

C개를 설치할 수 있는 최대의 길이를 구할 수 있다 (Upper Bound)

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int C = sc.nextInt();
		int[] arr = new int[N];
		for(int i=0;i<N;i++) {
			arr[i]=sc.nextInt();
		}
		Arrays.sort(arr);
		int min=1;
		int max=arr[N-1]-arr[0]+1;
		while(min<max) {
			int count = 1;
			int mid = (min+max)/2;
			int start = arr[0];
			for(int i=0;i<N;i++) {
				if(arr[i]>=start+mid) {
					count++;
					start=arr[i];
				}
			}
			if(count>=C) {
				min=mid+1;
			}else {
				max=mid;
			}
		}
		System.out.print(min-1);
}}