백준 2110번 공유기 설치 :: 마이구미

이 글은 백준 알고리즘 2110번 "공유기 설치" 를 풀이한다.

풀이 방법으로는 이분(이진) 탐색을 사용한다.

문제 링크 - https://www.acmicpc.net/problem/2110

이분 탐색 - http://mygumi.tistory.com/72

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

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

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

이 문제는 파라메트릭 서치 알고리즘을 적용한다고 알려져있다.

사실상 단순히 이분 탐색의 응용 문제라고 생각하면 된다.

문제가 원하는 것은 가장 인접한 두 공유기 사이의 거리가 최대이길 원한다.

이것은 모든 공유기들의 사이 간격이 공평하게 설치되기를 바라는 것을 의미한다고 볼 수 있다.

예를 들어, 공유기 사이의 최소, 최대 거리의 범위는 다음과 같다.

Input - 1 2 4 8 9
min => 1
max => 9 - 1 = 8

이러한 경우를 찾기 위해서는 순수하게 생각하면, 공유기간의 간격(min ~ max) 인 각 간격을 기준으로 모든 집 좌표들을 확인해보면 된다.

하지만 좌표의 수의 최대값이 1000000000 이라서 시간 초과를 경험할 수 있다.

즉, 단순한 탐색(O(n^2)) 으로는 해결 할 수 없다.

시간을 줄이기 위해 우리는 이분 탐색을 사용할 수 있다.

각 간격을 기준으로 일일이 확인하는 것이 아닌 이분 탐색의 방식을 이용하는 것이다.

1. 특정 간격을 기준으로 가능한 위치에 공유기를 설치한다.
2. 설치한 후에는 다음과 판단한다.
3. 공유기 수가 더 설치되어야 한다면, 간격을 줄인다.
4. 공유기 수를 줄여야한다면, 간격을 늘린다.

위 과정을 반복하여 원하는 간격을 얻어낸다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/binarysearch/2110.java

private void solve() {
    int n = sc.nextInt();
    int c = sc.nextInt();
    int[] array = new int[n];
 
    for (int i = 0; i < n; i++) {
        array[i] = sc.nextInt();
    }
 
    Arrays.sort(array);
 
    int left = 1; // 가능한 최소 거리
    int right = array[n - 1] - array[0]; // 가능한 최대 거리
    int d = 0;
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2; // 기준
        int start = array[0];
        int cnt = 1;
 
        // 간격(d) 를 기준으로 공유기 설치
        for (int i = 1; i < n; i++) {
            d = array[i] - start;
            if (mid <= d) {
                ++cnt;
                start = array[i];
            }
        }
 
        if (cnt >= c) {
            // 공유기의 수를 줄이자 => 간격 넓히기
            ans = mid;
            left = mid + 1;
        } else {
            // 공유기가 더 설치되어야한다. => 간격 좁히기
            right = mid - 1;
        }
    }
    System.out.println(ans);
}