백준 2110.cpp (매개변수 탐색)

개 킹 받는 매개변수 탐색 문제 풀이를 자세하게 작성해보았다.

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

이 문제에서 요구하는 건 어떤 두 공유기 사이의 거리를 최대로 만드는 것이다. 즉 구하고자 하는 건 두 공유기의 최대 거리이다.

 

구하고자 하는게 공유기의 거리라는 걸 알았으니 자연스럽게 left, right (또는 low, high)의 범위를 지정할 수 있다. left와 right는 공유기 거리의 최소, 최대 값이다. 문제 조건에서 집 좌표가 0 ~ 10억이라고 했으니, 공유기의 거리는 최소 0에서 10억임을 알 수 있다. (그럼 left = 0, right = 10억으로 설정하면 되겠군!)

 

+ 한 가지 문제가 있다. 집의 좌표가 뒤죽박죽인데 집의 순서가 공유기 거리에 영향을 줄까? 그렇지 않다. 각 집의 좌표가 중요한 것이지 집의 순서가 중요한 것이 아니다. 그리고 공유기를 첫 번째 집에 설치해줘야 뒤에 이어서 다른 집들과 비교해보기 편하다. 또한 첫 번째 집에 설치할 때 문제가 없으려면 첫 번째 집의 좌표 값이 가장 작거나 가장 커야 답을 구하는데 영향이 없을 것이다. 따라서 오름차순 또는 내림차순으로 정렬이 필요하다.

 

굿.. 이제 매개변수 탐색을 구현하면 된다. 먼저 변수들을 설정한다.

• mid = (left + right) / 2
  • 최대 거리 (비교를 위한 기준 거리)
• c = C - 1
  • 첫 번째 집에 공유기를 설치하므로 공유기 수에서 한 개를 먼저 뺀다
• dist = house[0]
  • 공유기의 거리 (최초에는 첫 번째 집의 좌표로 설정. 이후 다른 집들과 비교)

left와 right가 변하면서 mid로 최대 거리들을 탐색해볼 텐데, 만약 현재 두 집의 거리가 mid보다 크거나 같다면 해당 집에 공유기를 설치해본다는 조건을 설정하자. (왜냐하면 우리는 최댓값을 구하는 것이기 때문)

 

그리고 공유기의 숫자가 0개가 되면 공유기 설치를 그만하고 right를 감소시킨다는 조건을 추가하자. (공유기가 모두 설치되었다는 것은 mid(기준 거리)가 충분히 작다는 의미이기 때문)

 

반대로 공유기 설치가 끝났는데 공유기가 남았다면 left를 증가시킨다는 조건을 추가하자. (공유기가 모두 설치되지 않았다는 것은 mid(기준 거리)가 너무 크다는 의미이기 때문)

 

이렇게 생성한 조건들을 코드로 구현하면 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, C, house[200000];

int main() {ios_base::sync_with_stdio(0); cin.tie(NULL);
    cin >> N >> C;

    for(int i = 0; i < N; i++)
        cin >> house[i];

    sort(house, house + N);

    int left = 0, 
        right = (int)1e9, 
        mid, 
        dist, 
        c, 
        ans;

    while(left <= right) {
        mid = (left + right) / 2;   // 기준 거리
        c = C - 1;                  // 공유기 수
        dist = house[0];            // 공유기의 거리

        for(int i = 1; i < N; i++) { // 배열을 순회하면서 기준에 맞으면 공유기를 설치해본다
            if(house[i] - dist >= mid) { // 조건 : 기준 거리보다 거리가 멀거나 같으면 설치한다
                dist = house[i];
                c--;
                if(c == 0) break;
            }
        }
        if(c > 0) { // 공유기를 설치하지 못했으면 기준 거리가 너무 먼 것이므로
            right = mid - 1;
        } 
        else { // 공유기를 다 설치했으면 기준 거리가 충분히 좁은 것이므로
            left = mid + 1;
            ans = mid;
        }
    }
    cout << ans;
}