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

문제

 

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

---

Algorithm

임의의 두 공유기 사이의  거리를 늘리게 되면, 이외의 공유기와의 거리가 가까워질 수 있으므로 최대한 평등하게 설치하는 것이 핵심 아이디어다.

이분탐색을 진행하여, 가장 왼쪽부터 시작해 공유기를 설치한 집으로부터 임의의 수 k이상 떨어진 집에 설치하는 것을 반복한다.
더 이상 설치할 수 없는 경우, 설치한 공유기의 개수가 c개 이상이라면 k를 줄인 후 재설치한다.
c개 미만이라면, k를 키워 재설치한다.

이분탐색이 끝난 후의 k가 출력 답안이 된다.

 

---

 

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,c;
vector<int> home;


void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> c;
    for(int i = 0; i < n; i++)
    {
        int x; cin >> x;
        home.push_back(x);
    }
}


void SOLVE()
{
    sort(home.begin(),home.end());

    int left = 1, right = home[n-1];

    int ans;
    while(left <= right)
    {
        int mid = (left + right) / 2;

        int setIdx = home[0];//가장 마지막에 설치한 집의 위치
        int cnt = 1;//가장 왼쪽 집에는 무조건 설치
        for(int i = 1; i < n; i++)
        {
            //공유기로부터 mid 이상 떨어져있다면 설치
            if(setIdx + mid <= home[i])
            {
                setIdx = home[i];
                cnt++;
            }
        }

        if(cnt < c) right = mid - 1;
        else ans = mid , left = mid + 1;
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}