백준 2110 공유기 설치

www.acmicpc.net/problem/2110

2110번: 공유기 설치

이 문제 해결에 앞서 이분탐색에 대해 기본 개념을 익히고자 한다면, 다음의 포스팅을 한번 살펴보기 바란다.

이분탐색 : t-anb.tistory.com/18

이분탐색

 

이분탐색의 기본 문제이다. 이분탐색 실전 문제 해결 능력 향상을 위해 정리하였다. 

먼저 문제의 예제를 그림으로 표현하였다.

집1~5의 좌표: 1, 2, 4, 8, 9

집은 일직선(1차원)상에 놓여있기 때문에, 한쪽 끝에는 항상 1개의 공유기가 있다고 생각할 수 있다. 그래서 집 1에 공유기가 있다고 가정하고, 한 개씩 보면서 거리를 측정하고 공유기를 설치할 만큼 이격 되어 있는지를 판단하면 된다. '두 집간의 거리가 3 이상일 때, 공유기를 설치한다'라고 한다면, 집 1과 집 2간의 거리는 1밖에 안되므로 설치가 불가하다. 다음 집인 집 3을 봤을 땐 거리가 3이므로 설치가 가능해진다.

그러면 이제 집 3에 공유기를 설치하고, 그 다음의 집들은 집 1이 아니라 집 3과의 거리 차이를 보는 것이다. 집 4는 집 3과 4만큼 떨어져 있어서 또 설치가 가능하다. 집 5는 가까워서 설치가 안되기 때문에, 총 3개의 공유기가 설치 가능하다. 

 

이런 방식으로 모든 집을 순회하면서 거리를 확인하고 설치한 공유기의 총 갯수와 문제의 C와 비교하여 너무 많이 설치했다면 공유기 간 거리를 늘려주고, 적었다면 공유기 간 거리를 줄여주면 된다. 

위와 같이, 전체 범위를 잡고 그안에서 중앙값 mid를 설정한 후에 설치 가능한 공유기 개수를 모두 세어보았을 때(변수 cnt), 그 값(cnt)이 C보다 작다면, mid자체를 포함하여 그보다 큰 값들은 전부 버릴 수 있게 된다. 공유기 간 거리를 줄여야 cnt가 늘어날 것이기 때문이다. 

그리고 그를 의미하는 것이 e = mid 이다.

다음 mid계산에 앞서 상한 값을 mid로 변경함으로써, 이제 mid이상의 값이 선택될 일은 없도록 제한하는 것이다.

집들의 좌표는 1에서 10억 사이에 있게 된다. 큰 범위다. 하지만 이분탐색시에 10억이란 범위도 30번 만에 모두 확인할 수 있다. 즉, 30번만 mid를 선택하면, 답을 구할 수 있다는 것이다! 그리고 매 선택 시 모든 집을 순회(20만 개의 집)하기에, (while 루프 30번, 매 회당 20만 번)

 

시간복잡도는 (N log x) = (20만 x 30) = 600만이 된다. 6백만 번의 연산이면 시간 내에 해결 가능하다.

(N은 집의 개수, x는 집의 좌표 범위)

 

<주요 내용>

이분탐색, N log x

 

<코드>

이분탐색 문제에서 항상 까다롭고 주의할 부분은 가장 마지막 처리이다. 

보통 while루프를 통해 s 또는 left가 e 또는 right와 같거나 넘어갈 때까지 반복하게 되는데, 마지막에 나온 한 개의 값이 답인지 아니면 답에 한 개 모자란 것인지를 판단하는 것이 어려울 수 있다. 

 

이분탐색 문제에서는 단 한 개의 값을 찾을 때도 있지만, 보통 '어떠한 조건을 만족하는 최대/최소값'을 찾는 문제들이다. 그렇다면 어떠한 범위에 들어가는 값들은 모두 조건을 만족한다는 것이다. 이는 mid 선택 후 계산한 결과와 문제의 조건을 비교할 때 (위의 예시에서는 cnt와 C를 비교할 때), 등호를 어디에 붙일 것이냐와 관련된다.

등호가 붙었을 때 mid는 사실상 정답의 범위에 있었다는 것인데, 이때 mid를 버린다면 마지막에 while루프를 통과하고 나오는 하나의 값은 정답의 범위를 1만큼 넘거나 1만큼 모자라다는 뜻이 되는 것이다. 

이를 설정하는 건 사람마다 각기 다른 노하우가 있고, 문제 상황에 따라서도 달라질 수 있으니, 일률적으로 고정된 코드를 붙이기는 힘들다.

import sys
si = sys.stdin.readline


def main():
    [n, c] = [int(e) for e in si().split()]
    coords = []
    for _ in range(n):
        coords.append(int(si()))
    coords.sort()

    s, e = 1, 10**9
    while s != e:
        mid, cnt, prev = (s+e)//2, 1, coords[0]
        for elem in coords:
            if elem-prev >= mid:
                cnt += 1
                prev = elem
        if cnt >= c:
            s = mid+1
        else:
            e = mid
    print(s-1)


if __name__ == '__main__':
    main()

 

아래는 C++코드이다.

#include <iostream>
#include <algorithm>
#define endl '\n'
#define nMax 200000
using namespace std;

int n, c;
int arr[nMax];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int d, temp, s, e, cnt, mid;
    cin >> n >> c;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    if (c == 2)
    {
        cout << arr[n - 1] - arr[0] << endl;
        return 0;
    }

    s = 1;
    e = arr[n - 1];
    while (s < e)
    {
        cnt = 1;
        mid = (s + e + 1) / 2;
        temp = arr[0];
        for (int i = 0; i < n; ++i)
        {
            d = arr[i] - temp;
            if (d >= mid)
            {
                cnt++;
                temp = arr[i];
            }
        }
        if (cnt >= c)
            s = mid;
        else
            e = mid - 1;
    }
    cout << e << endl;
    return 0;
}