백준 2110. 공유기 설치 (이분탐색)

www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제제목 : 공유기 설치

문제유형 : 이분탐색

문제난이도 : 실버1

 

문제

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

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

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

입력

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

출력

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

아이디어

문제를 읽었을 때, 문제가 이해가 안돼서 힘들었던 문제이다...

해당 문제에서 주어진 TC에서,

[1 2 - 4 - - - 8 - 9 ] 일때 출력이 3이라는데, (1,4,9)에 설치해서 4와 9사이는 5인데.. 하면서 뭔 소린가 한참 해맸었다.

결국 블로그를 참고하게 되었는데, 최대 거리가 4이면 (1,8)을 선택할 수 밖에 없으니 안되고

최대거리가 3이면 (1,4,8)도 되고, (1,4,9)도 가능하게 된다. 

최대 거리가 2면 (1,4,8), (1,4,9)이렇게 공유기 3개 설치가 가능한데, 최대거리를 구하는 것이므로 3을 출력해준 것이다.

 

따라서, 공유기를 설치할 수 있는 집의 최소 거리는 1이고

최대 거리는 (가장 먼 집 - 가장 가까운 집)이 된다.

 

최소 거리부터 최대거리까지 포문을 돌리는 것 보다 이분탐색을 이용하여 탐색하는 것이 효율적이므로

이분탐색을 이용하면 된다.

 

package week6;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ2110 {
	public static int N;
	public static int C;
	public static int[] distance;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		
		distance = new int[N];
		for (int i = 0; i < N; i++) {
			distance[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(distance);
		
		int min = 1; // 최소 간격
		int max = distance[N-1] - distance[0]; // 최대간격
		
		int result = 0; // 결과 (최대 거리)
		int last_set = 0; // 가장 마지막에 공유기를 설치한 집
		
		while (min <= max) {
			last_set = distance[0];
			int count = 1; // 공유기 개수 1 : 첫번째 집에는 설치
			int mid = (max + min) / 2;
			
			for (int i = 1; i < distance.length; i++) {
				if (distance[i] - last_set >= mid) {
					last_set = distance[i];
					count++;
				}
			}
			
			if (count >= C) {
				result = Math.max(result, mid);
				min = mid + 1;
			} else { // 해당 거리로 공유기를 설치할 경우, 공유기가 남아서 탐색할 거리를 좁혀준다.
				max = mid - 1;
			}
		}
		System.out.println(result);
	}
}

 

어제 밤에 풀다가 도저히 모르겠어서 문제만 이해하고 오늘 다시 도전해봤는데 은근 쉽게 풀린 문제.

빨리 실버문제는 껌으로 풀면서 골드문제로 넘어가고 싶다 ㅠ_ㅠ... 알고리즘 어려워