공유기 설치

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

 

C개의 공유기를 N개의 집에 적당히 설치해서,

"가장 인접한 두 공유기" 사이의 "거리를 최대로" 하는 프로그램을 작성

 

 

<소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int n, m, num, st, router;
    cin >> n >> m;
    vector<int> pos;
    pos.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i];
    }
    // 이분 탐색을 하기위한 정렬
    sort(pos.begin(), pos.end());
    
    // 인접한 공유기 사이가 mid 이상이 되도록 
    // 공유기를 m개 이상 배치할 수 있는가?
    // T T T .. F F -> left가 정답
    int left = 1;                          // 최소 거리 -> Check T
    int right = pos[n - 1] - pos[0] + 1;   // 최대 거리 -> Check F
 
    while (left + 1 < right) {
        int mid = (left + right) / 2;
 
        // 첫번째 집에 공유기 설치
        st = pos[0];
        router = 1;
        for (int i = 1; i < n; i++) {
            if (pos[i] - st >= mid) {
                router++;
                st = pos[i];
            }
        }
 
        if (router >= m)
            left = mid;
        else
            right = mid;
    }
    cout << left;
    return 0;
}