백준 2110 (공유기 설치)

문제

---

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

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

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

 

 

 

 

풀이

---

정확하게 이분탐색 또는 N분탐색 문제 유형을 이해하는 건 어렵다.

이문제도 풀이를 보기 전까진 왜 이분탐색으로 풀어야하는지 감을 못잡았다.

 

해설을 찾아보니 이문제는 공유기를 두는 집에 집중하는 것이 아닌 인접한 두개의 집의 거리에 집중해서 풀어야한다. 그러니 최소값을 1 로두고 최댓값은 현재 집의 좌표중 가장 큰값으로 두고 이분탐색을 통해 찾아가면 된다.

여기서 중요한건 이분탐색으로 찾는건 공유기간의 거리(distance)다. 어느 좌표의 집에 공유기를 설치하는 것이 중요한게 아니다.

 

이분탐색으로 찾아진 거리를 집의 좌표에 대입했을때 해당 공유기 개수를 모두 넣을 수 있을만큼 또는 더 넣을 수 있을 만큼의 거리가 최대거리가 된다.

 

쉽게말해 이분탐색으로 구해진 최적의 거리를 집의 좌표에 맞게 대입을 했을때 집의 좌표에 각각 맞게 넣었을 때 공유기를 모두 사용 할 수 있으면 된다.

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] num = br.readLine().split("\\s");
		int n = Integer.parseInt(num[0]);
		int c = Integer.parseInt(num[1]);
		
		List<Integer> houses = new ArrayList<Integer>();
		for(int i = 0 ; i < n ; i++) {
			houses.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(houses);
		
		long count = 0;
		long right, left, mid, maxLen = 0;
		int prev;
		right =  houses.get(n - 1);
		left = 1;
		
		while(left <= right) {
			count = c - 1;
			mid = (left + right) / 2;
			
			prev = houses.get(0);
			for( int i : houses ) {				
				if(i - prev >= mid) {
					prev = i;
					count--;
				}
			}	
			
			if(count <= 0 ) {
				if(mid > maxLen) {
					maxLen = mid;
				}
				
				left = mid + 1;
			}
			else{
				right = mid - 1;
			}
		}
		
		sb.append(maxLen);
		System.out.println(sb);
	}
}