BOJ 2110번 공유기 설치

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

github : https://github.com/junho0956/Algorithm/blob/master/2110/2110/%EC%86%8C%EC%8A%A4.cpp

 

C개의 공유기를 N개의 집에 남김없이 설치해야하는 문제이다.

** 설치가 가능할 때 집과 집 사이의 거리중 가장 인접한(작은) 거리를 최대로 만드는 문제이다. **

코드와 함께 이분탐색의 조건을 같이 주석처리 해놓았다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, c, x;
    vector<int> v;
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
 
    int left = 1, right = v[n - 1] - v[0];
    int result_len = 0;
 
    while (left <= right) {
        int len = (left + right) / 2;
        int cnt = 1, last_house = 0;
        int min_len = INT_MAX;
        bool check = false;
        for (int i = 1; i < n; i++) {
            if (v[i] - v[last_house] >= len) {
                min_len = min(min_len, v[i] - v[last_house]);
                cnt++, last_house = i;
                if (cnt == c) {
                    check = true; break;
                }
            }
        }
        // 공유기 c개를 설치할 수 있다면 -> 현재 len 보다 더 큰 값을 
        if (check) {
            result_len = max(result_len, min_len);
            left = len + 1;
        }
        // 공유기 c개를 설치할 수 없다면
        else right = len - 1;
    }
    cout << result_len;
    return 0;
}