[백준 1477번] [이분 탐색] 휴게소 세우기

사실상 백준 2792번 보석상자와 다른 부분이 하나도 없다. 물론 정렬하기는 해야한다는 점에서 차이가 아얘 없지는 않다.

viyoung.tistory.com/186

[백준 2792번] [이분 탐색] 보석 상자

특정한 숫자 간격을 얼마만큼 형성할 수 있는지를 묻는 것이므로 근본적으로 나눗셈과 관련이 되어있다.

적당히 몫과 나머지를 보고 연산을 해주면 된다.

 

기존에 있는 주유소에는 다시 설치할 수 없으므로 나머지가 0인 경우에는 몫에서 - 1개만큼의 신규 주유소를 지을 수 있는 것이고

아닌 경우에는 몫만큼 신규 주유소를 지을 수 있다.

 

추가적으로 만족하는 최댓값 중 최솟값을 구하는 상황이므로 lower_bound를 써서 구해주면 된다.

무조건적으로 해당하는 숫자가 있을 수 밖에 없으므로 end값을 크게 신경쓰지 않아도 되고, 존재하지 않는 경우에 대해 따로 예외처리를 진행하지 않아도 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    int n, m, l;
    cin >> n >> m >> l;
    vector<int> data;
    vector<int> length;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        data.push_back(temp);
    }

    sort(data.begin(), data.end());

    length.push_back(data[0]);

    for(int i = 1; i < data.size(); i++){
        length.push_back(data[i] - data[i - 1]);
    }

    length.push_back(l - data[data.size() - 1]);

    sort(length.begin(), length.end());

    int start = length[0];
    int end = length[length.size() - 1];

    while(start < end){
        int mid = (start + end) / 2;
        int count_store = 0;

        for(int i = 0; i < length.size(); i++){
            if(length[i] % mid == 0){
                count_store += length[i] / mid - 1;
            }
            else count_store += (length[i] / mid);
        }

        if(count_store > m){
            start = mid + 1;
        }
        else end = mid;
    }

    cout << start << "\n";
    return 0;
}