[BOJ/c++] 2110 - 공유기 설치

문제

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

2110번: 공유기 설치

풀이

집의 개수가 최대 20만개이고 집의 좌표가 10억까지 가능하므로 이진탐색으로 풀어야 한다.

1. 공유기 좌표를 정렬

2. 정렬된 공유기 좌표에서 가장큰 좌표와 가장 작은 좌표의 차이가 가능한 최대값

3. st = 1, ed = (가장 큰 집의 좌표 - 가장 작은 집의 좌표)로 두고 이진 탐색을 한다.

4. 첫번 째 집에는 무조건 공유기를 설치해야 하고 모든 집들을 방문하면서 이전에 공유가 설치된 집과의 거리 차이가 mid값보다 크거나 같으면 공유기를 설치한다.

5. 원하는 공유기 수만큼 설치를 못했으면 ed = mid - 1 아니라면 st = mid + 1 (원하는 만큼 설치를 했어도 최대값을 구하기 위해 mid를 증가시킨다)

코드

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

#define ll long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    cin >> n >> c;
    vector<ll> v;
    for (int i = 0; i < n; i++) {
        ll p;
        cin >> p;
        v.push_back(p);
    }
    sort(v.begin(), v.end());
    ll st = 1; ll ed = v[n - 1] - v[0];
    ll ans = 0;
    while (st <= ed) {
        ll mid = (st + ed) / 2;
        int cnt = 1; int prev = 0; ll tmp = 1000000000;
        for (int i = 1; i < n; i++) {
            if (v[i] - v[prev] >= mid) {
                tmp = min(tmp, v[i] - v[prev]);
                prev = i;
                cnt++;
            }
        }
        if (cnt < c) {
            ed = mid - 1;
        } else {
            st = mid + 1;
            ans = max(ans, tmp);
        }
    }
    cout << ans;
    return 0;
}