백준 2110번 공유기 설치 // C++

문제

공유기 설치

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

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

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

입력

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

출력

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

---

풀이

연속한 공유기 간의 거리의 차이가 최대가 될 때의 거리를 구하면 된다.

 

Binary Search를 이용하여 거리의 최댓값을 구하면 되는데, 거리를 구하는 방법은 다음과 같은 두 가지 경우로 나뉜다.

 

설치해야 하는 공유기의 수가 N개이고 현재 거리가 X일 때,

• 설치 가능한 공유기의 수가 N개 이상 : X의 값을 더 크게(left = mid + 1)
• N개보다 작음 : X의 값을 더 작게(right = mid - 1)

또한, 거리에 따른 공유기의 개수를 세기 위하여 prev 변수를 사용하여, 공유기를 마지막으로 설치한 장소를 저장하였다.

prev과 현재 index의 차이가 mid(현재 비교하는 거리) 이상이라면 설치가 가능하다는 것을 의미한다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, C;
vector<int> home;

void input();
void solve();

int main() {
    int n;

    input();

    solve();
}

void input() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N >> C;

    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;

        home.push_back(num);
    }

    sort(home.begin(), home.end());
}

void solve() {
    int answer = 1;

    int count = 0;
    int left = 1; // 최소 거리
    int right = home[N - 1] - home[0]; // 최대 거리
    int mid;
    int prev;

    while (left <= right) {
        prev = 0;
        count = 1; // 시작 점은 항상 true이기 때문

        mid = (left + right) / 2;

        for (int i = 1; i < N; i++) {
            if (home[i] - home[prev] >= mid) { // 이 전의 공유기 위치와 비교
                count++;
                prev = i;
            }
        }

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

    cout << answer;
}