[C++/Binary Search]백준 2110 공유기 설치

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool check(vector<int> v, int dist, int c){
    int cnt = 1; // 맨 첫번째에 놓여있는 공유기 
    int last = v[0] + dist; // 첫번째 다음에 놓일 공유기
    
    for(int i = 0; i < v.size(); i++){
        if(v[i] >= last){ // 최소 거리보다 멀리 있는 집인 경우
            cnt++; // 공유기 1대 설치
            last = v[i] + dist; // 다음에 놓일 공유기 위치
        }
    }
    
    // 현재 공유기 개수(cnt)가 c보다 같거나 클 경우, 최소 거리를 늘릴 수 있고 -> true 리턴
    // 현재 공유기 개수가 c보다 작을 경우, 최소 거리를 줄여야 함 -> false 리턴
    return cnt >= c;
}
 
int main() {
    int n, c;
    cin >> n >> c;
    
    // 집 정보 입력
    vector<int> v;
    v.resize(n);
    
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end()); // 집 정보 정렬
    
 
    // 공유기 간 최소 거리를 구하기 위한 binary search 실행
    int start = 1; // 가장 적은 공유기간 거리
    int end = v[n-1] - v[0]; // 가장 큰 공유기간 거리
    int ans = 1; 
    
    while(start <= end){
        int mid = (start + end) / 2;
        if(check(v, mid, c)){ // 공유기가 c보다 같거나 적게 는 경우
            ans = max(mid, ans);
            start = mid + 1;
        }else{ // 공유기가 c보다 많이 드는 경우
            end = mid - 1;
        }
    }
    cout << ans << endl;
}