백준 2210번: 공유기 설치

---

가장 인접한 두 공유기 사이의 최대 거리를 출력해야 하는 문제다. 즉, 최소 거리가 최대가 될 때의 거리를 구해야 한다.
(가장 약한 놈이 그나마 제일 강할 때를 구하라)

잘못된 첫 접근법

n개의 집에 c개의 공유기를 설치할 때, 가장 인접한 두 공유기 사이의 거리는 공유기 배치를 어떻게 하냐에 따라 달라진다. 그러므로 공유기 배치를 어떻게 할까에 집중했다.

그런데, 도저히 내 머리로는 일정한 규칙을 찾을 수가 없었다.
그나마 내가 생각해낸 아이디어는, 첫 번째 집과 마지막 집에는 공유기를 설치한 상태로 시작하자 정도였다.

하지만, 중간중간에 어떤 집에 공유기를 설치할지에 대해서는 생각해내지 못 하고 결국 풀이법을 찾아봤다.

올바른 접근법

이 문제는 결국, 구해야 하는 최소거리에 집중해야 한다.

우리가 설정한 최소거리 t에 따라 설치할 수 있는 공유기 수가 정해지게 되는데, 우리는 t가 최소 거리중 최대일 때를 찾아내는 것이다.

이렇게 t의 값을 바꿔가며 답을 찾아내는 것이고, t를 바꿔가는 과정에서 이분 탐색을 사용할 것이다.

결국 핵심은 다음과 같다.

0. 입력받은 좌표를 오름차순 정렬하고, 첫 번째 집에 공유기를 설치한 상태에서 시작한다.
1. 최소거리 t를 설정한다.
2. i번째 공유기를 설치한 집으로부터 t 이상의 거리를 두고 있는 집 중, 가장 가까운 집에 i+1번째 공유기 설치한다.
3. 마지막 집까지 2번 과정을 반복한 뒤에 설치된 공유기 수를 확인한다.

이때, 설치된 공유기 수와 가지고 있는 공유기 수를 비교한다.
(가지고 있는 공유기 수는 문제에서 입력값 c로 주어진다.)

• 설치된 수 > 가지고 있는 수 : 최소거리를 작게 설정했기 때문에 가지고 있는 공유기의 수보다 많은 양을 설치하게 된다. -> 최소거리를 늘린다.
• 설치된 수 < 가지고 있는 수 : 최소거리를 크게 설정했기 때문에 가지고 있는 공유기를 다 못 쓰게 된다. -> 최소거리를 줄인다.
• 설치된 수 == 가지고 있는 수 : 우리가 결국 구해야 하는 상황인 최소 거리가 최대일 때인지 알 수 없기 때문에 -> 최소거리를 늘린다.

이분 탐색 + 매개 변수 탐색의 과정이다.

중요한 점은, 설치된 수가 c와 같아져도 최대인지 알 수 없기 때문에 최소 거리를 늘리면서 최대일 때를 찾는다는 것이다.

결국, 조건을 부합(설치된 수 == 가지고 있는 수)하지 않기 직전 값을 구하면 된다.

Code

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

public class Main {
    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[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arr);

        int lo = 1; // 가능한 최소 간격
        int hi = arr[n - 1]; // 입력받은 집들의 최대 간격

        while (lo <= hi) {
            int mid = (lo + hi) / 2; // 최소 거리 설정

            int position = 0; // 공유기 설치 위치(처음부터 시작)
            int cnt = 1; // 설치 가능한 공유기 수
            for (int i = 1; i < n; i++) {
                if (arr[i] - arr[position] >= mid) {
                    position = i;
                    cnt++;
                }
            }

            if (cnt < c) { // 설치된 공유기 수가 가지고 있는 공유기의 수보다 적으면
                hi = mid - 1; // upper bound 내림으로써 최소 거리 줄인다.
                continue;
            }
            
            //설치된 공유기 수가 가지고 있는 공유기 수보다 크다면
            lo = mid + 1; // lower bound 올림으로써 최소 거리 늘린다.
            
        }

		// 설치한 수 == 가지고 있는 수가 되었을 때 while문을 끝내지 않고
        // 설치한 수 < 가지고 있는 수가 될 때가 되었을 때 끝냈기 때문에
        // 최소 거리의 최대(조건을 부합하지 않기 직전) 값을 출력하기 위해 1을 빼준다.
        System.out.println(lo - 1);
    }
}