문제

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

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

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

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

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

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

예제 입력 1
5 3
1
2
8
4
9

예제 출력 1
3

접근

이 문제를 풀면서 내가 이분 탐색을 개못한다는 사실을 깨닫게 되었다....^^
xi 값이 워낙 크니까 이분 탐색으로 접근해야겠다는 생각은 했는데, 이분 탐색을 너무 황당... 하게 했었다.
처음에 접근을,,, 너무 황당한(극히 일부 케이스에만 적용되는) 전제를 깔고 해버렸다.
그러니까 나는, 두 공유기 사이의 거리가 최대가 되도록 새로운 공유기를 고르려면, 범위 내 가장 작은 좌표와 가장 큰 좌표 사이를 딱 반으로 나누는 중간값에 최대한 가까워야 할 거라고 생각했다. 그래서 중간값에 가까운 집을 선택하고, 또 집과 집 사이 범위 내에서 가장 중간값에 가까운 집을 모두 찾은 후 그중 최대가 되는 집을 선택하고... 이렇게 선택하는 방식을 C번 반복하면 되지 않을까? 생각했다. 너무 일차원적인 생각이었지.....^^
문제는 그 범위 내에 공유기를 딱 하나만 설치하지 않을 수도 있다는 거였다.

예를 들어서, 입력이 다음과 같이 주어졌다고 해보자.

10 4
1
2
3
4
5
6
7
8
9
10

이때 공유기를 두 공유기 사이의 거리의 최댓값은 3으로, 1, 4, 7, 10에 설치해야 한다.
그런데 내가 생각한 방식으로 하면 시작부터 1과 10의 중간값인 5나 6중에 하나를 선택하게 되어 버리고, 그러면 답과 달라진다.

---

이분 탐색의 기본 컨셉은 값을 하나 선택해본 후, 그 값을 박아 넣었을 때 정답이 될 수 있는지 없는지 확인한 다음 그 결과에 따라 범위를 조정하는 거다.
이 문제도 이 기본 컨셉에 맞게 접근했다면 이렇게 이상한 길로 새지는 않았을 텐데, 너무 오랜만에 이분 탐색을 해서 감이 다 죽은 것 같다ㅠ....

이 문제에서 구해야 하는 값은 공유기 C개를 설치할 수 있는 경우 중 가장 인접한 두 공유기 사이의 거리가 최대일 때의 값이다.
그러니 이 문제에서도 가장 인접해 있는 이 두 공유기 사이의 거리가 될 수 있는 모든 값들 중 하나를 선택해본 후, 그 값에 따라 공유기를 설치했을 때 C개를 설치할 수 있는지 없는지 확인하면 되는 거였다.
C개를 설치할 수 있으면 가장 인접해 있는 이 두 공유기 사이의 거리를 더 늘렸을 때도 C개를 설치할 수 있는지 확인하고, C개를 설치할 수 없으면 거리를 줄여서 다시 탐색하면 된다.
즉, 모든 경우 중 가능한 한 큰 값을 구해야 하니 Upper-Bound를 구하는 문제였다.

---

그렇다면 가장 인접해 있는 이 두 공유기 사이의 거리를 k라고 했을 때, 설치할 수 있는 공유기의 개수는 어떻게 구할까?
다른 분들의 풀이를 보니 일단 제일 왼쪽의 집에 설치하고, 그 이후부터 나오는 집들의 경우 직전 설치 위치에서 k 이상 떨어져 있으면 무조건 설치하는 식으로 구현을 하셨더라.

처음 풀이를 봤을 때는 k가 고정되어 있더라도 공유기를 어느 위치에 설치하느냐에 따라 설치할 수 있는 공유기의 개수가 달라질 텐데 이렇게 한 케이스만 봐도 되는 건가....? 하는 의아함이 있었다.
직전 설치 위치에서 k 이상 떨어져 있으면 무조건 공유기를 설치하게 되면, 당연히 가장 인접한 거리가 k인 여러 케이스들 중에서 가장 공유기를 많이 설치하는 케이스를 보게 될 것이다.
만약 가장 인접한 거리가 k일 때 설치할 수 있는 공유기의 개수의 최댓값이 C 이상이라면, k를 보다 늘려주더라도(즉, 인접한 공유기 사이가 더 떨어뜨려 놓더라도) 공유기 C개를 설치할 수 있는 가능성이 있다는 뜻이다.
이 문제에서는 최대한 큰 k를 구해야 하기 때문에 k를 최대한 늘리기 위해 공유기를 최대로 설치하는 것이다.

구현

구현은 그냥... Upper-Bound로 잘 구현하면 된다.

import java.io.*;
import java.util.*;

class Main {
    static long[] x;
    static int N;
    static int C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        x = new long[N];

        for (int i = 0; i < N; i++) {
            x[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(x);
        System.out.println(binarySearch(1, x[N - 1] - x[0]));
    }
    
    private static long binarySearch(long low, long high) {
        if (low > high) {
            return high;
        }
        long mid = (low + high) >> 1;
        int count = findMaxInstallation(mid);

        if (count >= C) {
            return binarySearch(mid + 1, high);
        }
        return binarySearch(low, mid - 1);
    }

    private static int findMaxInstallation(long minDistance) {
        int count = 1;
        int prev = 0;
        for (int i = 1; i < N; i++) {
            if (x[i] - x[prev] >= minDistance) {
                count++;
                prev = i;
            }
        }
        return count;
    }
}

이분 탐색 폐관 수련이 필요하겠다고 생각했다...