[백준] 2110. 공유기 설치 - 실버1

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

문제 요약

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

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

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

 

문제 해결 아이디어

어려운 문제였다. 일단 집과 집 사이의 거리가 될 수 있는 값 중에 최소값은 1, 최대값은 첫번째 집과 마지막 집의 거리라는 것을 놓고 그 사이의 값들에 공유기를 설치해서 최대값을 찾아야 한다.

min = 1, max = map[N-1] - map[0] << 이 사이 거리 중에 최대값을 이분 탐색으로 찾는다.

1. min이 max보다 같거나 작은 동안에

2. 첫번째 집에 공유기를 설치해 보고

3. 나머지 집들을 쭉 탐색해서 공유기가 설치된 집과의 거리가 최대 최소 사잇값보다 크다면 공유기를 설치할 수 있다고 가정해서 쭉 설치한다.

4. 이 과정이 완료되면 원하는 C개만큼의 공유기가 설치되었는지 확인하고, 만약 그대로 되었다면 더 넓은 거리에서 설치할 수 있는지 확인이 필요하다. 따라서 min값을 mid + 1로 바꿔준다.

5. 설치가 불가능하다면 더 좁은 거리를 확인해야 한다. max 값을 mid - 1로 바꿔 준다.

 

완성된 코드

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

public class Main {
	/*
	 * 228ms
	 */
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());

		int[] map = new int[N];

		for (int i = 0; i < N; i++) {
			map[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(map);

		// 집 사이의 거리 중 최소값은 1, 최대값은 첫번째 집과 마지막 집의 거리
		int min = 1;
		int max = map[N - 1] - map[0];
		int res = 0;

		// min 과 max 사이의 거리는 모두 가능성이 있으므로 그 거리들 중에 최대값을 이분탐색으로 찾아본다
		while (min <= max) {
			int mid = (min + max) / 2;
			int cnt = 1;
			int start = map[0];
			for (int i = 1; i < N; i++) {
				if (map[i] - start >= mid) { // map[i]와 공유기가 설치된 곳까지의 거리를 계산해 그 값이 mid보다 크다면 설치가 가능하다
					cnt++;
					start = map[i];
				}
			}

			if (cnt >= C) {
				res = mid;
				// 최대값을 찾아야 되니까 더 넓은 거리에서도 가능한지 확인해야 함. 이분탐색이므로 min값을 mid+1로 바꿔줌
				min = mid + 1;
			} else { // 설치 불가능
				// 더 좁은 거리에서 확인해야 함
				max = mid - 1;
			}
		}
		System.out.println(res);
	}
}