[백준/BOJ] 2110 공유기 설치

문제 : 2110 공유기 설치

2110번: 공유기 설치

집의 위치와 설치하는 공유기의 개수가 주어졌을 때,

가장 인접한 두 공유기 사이의 거리를 최대로 만들었을 때

그 거리를 출력하는 문제이다.

 최적으로 되도록 공유기를 설치했을 때 첫 번째 집에

공유기를 설치하지 않았다면 맨 왼쪽 집의 공유기를 첫 번째로 옮길 수 있으므로

첫 번째 집에 공유기를 설치하는 최적해가 언제나 존재한다.

따라서 첫 번째 집에 공유기를 설치했다고 가정한 후

이분 탐색을 통해거리의 최댓값을 찾으면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M;
vector<ll> arr;
ll f(ll x){
    ll cnt=1, chk=arr[0];
    for (int i=1;i<N;i++){
        if (arr[i]-chk>=x){
            cnt++;
            chk=arr[i];
        }
    }
    return cnt>=M;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<N;i++){
        ll a;
        cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(),arr.end());
    ll lo=1, hi=1000000001;
    while (lo+1<hi){
        ll mid=(lo+hi)/2;
        if (f(mid))
            lo=mid;
        else
            hi=mid;
    }
    cout << lo;
    return 0;
}