[C/C++] 백준 #2110 공유기 설치(이분 탐색)

N개의 집에 C개의 공유기를 적절하게 설치해서 두 공유기 사이의 거리를 최대한으로 하고자 할 때, 가장 인접한 두 공유기의 거리를 구하는 문제입니다.  이 문제는 이분 탐색을 이용해서 풀 수 있습니다.

 

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

2110번: 공유기 설치

 

이분탐색을 사용하기 위해서는 다음과 같은 조건을 만족해야 합니다.  (또는 그 반대이거나)

 

1. \(n\)에서 조건을 만족했다면, \(k \le n\)인 \(k\)에서도 조건을 만족한다.

2. \(m\)에서 조건을 만족하지 못 했다면, \(k \ge m\)인 \(k\)에서도 조건을 만족하지 못 한다.

 

이 전제조건을 만족한다면 이분탐색을 사용할 수 있습니다.  그래서 문제를 풀 때, 이 조건을 염두에 두고서 풀어야 합니다.

 

첫번째 left 값과 right 값을 설정했습니다.  left 값은 무조건 성공할 값이고, right 값은 무조건 실패할 값입니다.

이 문제에서는 left 값은 0으로, right 값은 가장 왼쪽 집과 가장 오른쪽 집의 거리를 c-1로 나눈다음에 1을 더했습니다.  이렇게 하면 똑같은 거리로 집들이 늘어서도 무조건 실패를 하게 됩니다.

 

조건은 설정된 값 이상으로 공유기를 설치하면 됩니다.  그래서 조건 검사는 c란 값이 현재의 거리값이면, c보다 크거나 같은 첫번째 집을 선택합니다.  이 때에도 c보다 크거나 같은 첫번째 집을 선택하는 것을 찾는 것도 이분탐색을 사용하면, 훨씬 빠르게 동작합니다.  저는 그냥 선형으로 찾았습니다.  첫번째 집 찾는 것도 이분탐색을 사용했다면, 숫자의 범위를 K, 공유기 개수를 C, 집의 개수를 N이라고 했을 때, \(O(C \log K \log N)\)의 복잡도로 찾을 수 있습니다.  선형으로 찾았다면, \(O( N \log K ) \) 로 찾을 수 있습니다.  만약 C의 값과 N의 값이 비슷하다면, 선형이 더 유리할 수 있습니다.  C의 값이 N의 값보다 작다면, 첫번째 집을 찾을 때 이분탐색이 더 유리합니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2110
//        - by Aubrey Choi
//        - created at 2019-11-20
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

int v[200000], n, c;
bool check(int s)
{
    int i, f=v[0], k=1;
    for(i=1;i<n;i++)
    {
        if(v[i]-f<s) continue;
        f=v[i]; k++;
    }
    return k>=c;
}
int main()
{
    int i, j;
    scanf("%d%d", &n, &c);
    for(int i=0;i<n;i++) scanf("%d", v+i);
    std::sort(v, v+n);
    i=0, j=(v[n-1]-v[0])/(c-1)+1;
    while(i<j-1)
    {
        int m=(i+j)/2;
        if(check(m)) i=m; else j=m;
    }
    printf("%d\n", i);
    return 0;
}

WiFi NAT