[BOJ 2110번/C++] 공유기

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

2110번: 공유기 설치

공유기

문제

문제

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

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

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

입력

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

출력

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

 

풀이

주어진 범위가 10억. 이렇게 큰 수의 범위에서는 이분탐색의 응용인 parametric search를 이용해볼 생각을 먼저 하는 것이 좋다.

 

우선, 공유기를 항상 첫 집에 하나 설치해준다고 하자.

우리가 구하고자 하는 것은 가장 가깝게 설치된 공유기 사이의 거리가 최대가 되는 값이다.

그 값을 d라고 한다면, 공유기는 항상 d보다 크거나 같은 간격으로 설치되어야 한다.

 

이 d값을 parametric search로 찾아내는 것이 핵심이다.

그렇다면 값이 변하는 기준을 정해주자.

 

집i의 위치를 house[i]라고 하자.

그러면, 그 집과 그 이전에 공유기를 설치한 집 사이의 간격은 house[i] - before_house 가 된다.

이 값이 mid보다 크거나 같은지를 비교하여 그 집에 공유기를 설치해도 되는지를 판단, 공유기를 설치한다.

그 후 설치된 공유기 수와 공유기의 수 C 둘을 비교해 탐색을 진행한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int house[200001];

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int N, C;
    cin >> N >> C;


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

    sort(house, house + N);

    int left = 0;
    int right = house[N - 1];
    int mid = (left + right) / 2;
    int answer = 0;

    while (left <= right) {
        int h = house[0];
        int count = 1;
        
        for (int i = 1; i < N; i++) {
            if (house[i] - h >= mid) {
                count++;
                h = house[i];
            }
        }

        if (count >= C) {
            left = mid + 1;
            answer = max(answer, mid);
        }
        else {
            right = mid - 1;
        }

        mid = (left + right) / 2;
    }

    cout << answer << endl;

    return 0;
}