1477 - 휴게소 세우기

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

정답을 미리 가정하고 정답의 범위를 점차 줄여나가보자.
만약 정답(휴게소가 없는 최대 구간)이 $x$라면 몇 개의 휴게소를 지어야할까?

길이가 $L$인 도로에는 $\{a_0, a_1, \dots, a_{n-1}\}$ 과 같이 휴게소가 있다고 하자.
최대 구간의 길이가 $x$라면 $a_0$과 $a_1$ 사이에는 $\frac{a_1-a_0-1}{x}$개 만큼의 휴게소가 필요하다.

$x$의 범위를 점차 줄여나간다면 휴게소의 개수($C_x$)가 원하는 $M$개 이상인 순간이 문제의 정답이다.

휴게소의 개수 $C_x$가 너무 많다면, 휴게소가 너무 많이 지어졌다는 의미이다. 너무 많이 지은 이유는 구간의 길이 $x$가 너무 좁았기 때문이다. $x$ 범위의 하한을 높이면 된다.
너무 적은 경우에는 반대로 $x$ 범위의 상한을 낮춘다.

도로의 처음과 끝 사이에도 휴게소를 세울 수 있으니 위치가 $0$인 곳과 위치가 $L$인 곳에도 가상의 휴게소가 있다고 생각하자.

#include <bits/stdc++.h>
using namespace std;

int count(vector<int>& v, int dist){
    int r = 0;
    for(int i=1; i<v.size(); ++i){
        r += (v[i] - v[i-1] - 1)/dist;
    }
    return r;
}

int main(){
    int n, m, L;
    scanf("%d %d %d", &n, &m, &L);
    vector<int> v = {0, L};
    for(int i=0; i<n; ++i){
        int k;
        scanf("%d", &k);
        v.push_back(k);
    }
    sort(v.begin(), v.end());
    int low=0, high=L;
    while(low <= high){
        int mid = (high+low)/2;
        if(count(v, mid) > m) low = mid+1;
        else high = mid-1;
    }
    printf("%d", low);
    return 0;
}