알고리즘 :: 백준 :: 이진탐색 :: 파라메트릭 서치 :: 2110 :: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C(2 ≤ C ≤ N)개의 공유기를 N(2 ≤ N ≤ 200,000)개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

문제접근

문제 풀이 전

• https://velog.io/@embeddedjune/이것이-코딩-테스트다-Part2-Chapter-7-이진-탐색 의 예제 2번 떡볶이 떡 만들기가 이 문제와 상당히 비슷한 문제다.
• C개의 공유기를 설치할 수 있는 모든 조합에 대해 N개의 집 사이의 모든 거리를 조사하는 bruteforce 방법으로는 결코 2초내에 해결할 수 없다.
• 그러므로 이 문제는 역으로 dist만큼의 거리를 설정한 뒤 C개의 공유기를 설치할 수 있는지 여부를 판단하는 파라메트릭 서치 문제로 변경해서 풀어야 한다!!
  • 파라메트릭 서치 문제로 변경하면 최대 $log_2(200,000) \approx 17번$만 판단하면 되는 문제로 변경된다.

문제 풀이

• 최대 간격은 0번 집과 N-1번 집 사이의 거리이다.
• mid 초기값은 $(N - 1 + 0) / 2$ 이며 이 간격을 기준으로 C개의 공유기를 설치할 수 있는지 판단한다.
• C개 이상 공유기를 설치할 수 있다면, 기준 간격을 늘려도 되므로 low = mid + 1 연산을 한다.
• C개 공유기를 설치할 수 없다면, 기준 간격을 줄여야 하므로 high = mid - 1 연산을 한다.

코드

// https://www.acmicpc.net/problem/2110
#include <iostream>
#include <algorithm>
using namespace std;

static int N, C, arr[200000];

bool isPossible(int dist) {
    int cnt = 1, prev = arr[0];
    for (int i = 1; i < N; ++i)
	// prev 집과 간격 비교했을때 dist 이상이면 
        if (arr[i] - prev >= dist) {
            cnt++;		// 공유기 설치 카운트 하고
            prev = arr[i];	// prev 집을 갱신한다.
        }
    if (cnt >= C) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> C;
    for (int i = 0; i < N; ++i) cin >> arr[i];

    sort (arr, arr + N);    // 좌표 순으로 정렬한다.

    // 파라메트릭 서치 문제로 변경
    int low = 1, high = arr[N - 1] - arr[0];
    int result = 0;
    while (low <= high) {
        int mid = (low + high) / 2;     // 기준 간격
        // <중요> 기준 간격으로 C개 이상 만들 수 있는지 검사한다.
        if (isPossible(mid)) {
            result = max(result, mid);
            low = mid + 1;      // C개 이상 만들 수 있으므로 low 증가
        }
        else high = mid - 1;    // C개 미만 만들 수 있으므므로 high 감소
    }
    cout << result << '\n';
}

결과