[BOJ] 2110번 - 공유기 설치

2110번 - 공유기 설치

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	13528	5996	4441	45.883%

문제

• 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 ${x_1, ..., x_N}$이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

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

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

입력

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

출력

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

예제 입력 1

5 3
1
2
8
4
9

예제 출력 1

3

출처

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

알고리즘 분류

• Parametric search
• 결정 문제
• Binary search 응용

접근 방법

문제를 읽고

1. 1차 접근 : Brute-Force식으로 풀 순 없을까? 모든 상황을 시뮬레이션 해보면 ? ${N}\choose{C}$ ==> TLE!

 

2. 2차 접근 : 단순하게 생각해보면 "2개의 집에 공유기를 설치했을 때 두 인접 공유기 간의 최대거리가 K일 때 C개의 공유기를 설치할 수 있을까? 이 경우 거리의 후보는 $[1,N]$까지의 구간의 크기인 N-1만큼 나오게 되고 각 구간마다 N번의 반복 => $O(N^2)$ ==> TLE.

 

3. 3차 접근 : 결정문제로 바꿔서 생각해보자, 결정함수 ß(x) = 두 인접 공유기 사이의 거리가 x일 때 설치할 수 있는 공유기의 개수가 C이상인가? 라고 뒀을 때 특정 k를 기준으로 참/거짓이 이분화된다. 조건함수 f(x) = 두 인접 공유기 사이의 최대거리가 x일때 설치가능한 공유기의 개수라고 가정 했을 때 f(x)는 다음과 같은 관계를 만족한다.  
   $f(x) \propto \frac{1}{x}$ 즉 f(x) 는 반비례 관계의 단조함수이다. 또한 K+1개의 공유기를 설치했을 때의 두 인접 공유기 사이의 최대거리와 K개의 공유기를 설치 했을 때의 최대거리는 같으므로( = 즉 결정함수도 단조함수 ) Parametric search 를 적용할 수 있다.
   더 엄밀한 증명은 링크 에서 확인해보자. 두 인접 공유기간의 거리와 공유기의 수는 반비례한다는 사실을 생각해보면 거리에 따른 공유기 수가 부족하면 거리를 좁혀서 탐색하고, 거리에 따른 공유기 수가 크거나 같을 경우 해당 거리에서 C개 이상의 공유기를 설치할 수 있으므로(=즉, 해의 범주에 들어감), 더 큰 거리가 있는지 탐색해본다(->최적해를 찾기 위해 )

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N,C;
vector<int> arr;
int installRouter( int max_dist ){
    // 최대 거리가 max_dist 가 되게 라우터를 깔 때 깔 수 있는 라우터의 수
    int router_cnt = 1;
    int prev = arr[0];

    for(int i=1; i<N; i++){
        if( max_dist <= arr[i] - prev ) {
            router_cnt += 1;
            prev = arr[i];
        }
    }
    return router_cnt;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> C;

    arr.resize(N);
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }

    sort( arr.begin(), arr.end() );

    int st = 1, end = arr[ arr.size() - 1 ] - arr[0];
    int ans = -1;
    while( st <= end ){
        int mid = (st+end)/2;
        int router_cnt = installRouter(mid);
        if( router_cnt < C )
            end = mid - 1;
        else{
            ans = mid;
            st = mid + 1;
        }
    }
    cout << ans;

    return 0;
}