2110: 공유기 설치

• toc {:toc}

2110: 공유기 설치 문제 확인하기

풀이

문제에서 요구하는 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하는 것은 결국 최대한 서로의 간격이 벌어지는 것을 의미하고, 최대한 벌어졌을 때의 간격에서 최소를 의미한다. 때문에 비슷한 간격을 설정하는 것이 중요하다고 생각했다.

1. 처음에는 주어진 집들의 간격을 전부 뽑아내야하나?
2. 처음, 끝을 공유기 설치하고 이분탐색하면서 mid를 설치할 집으로 선택하는 방식?

이렇게 생각했으나 시간적인 부분도 그렇고, 2번의 경우 뭔가 재귀적으로 코드를 작성해야할 것 같은데 될 것 같지 않았다. 1시간 정도 붙잡고 있어봤는데 아이디어가 떠오르지 않아 풀이를 찾아봤다. 알고리즘을 확인하고 코드는 스스로 작성해봤다.

아이디어 구조 굳이 입력받은 집들의 간격을 가지고 비교해 풀이할 필요 없고, mid를 최소 간격으로 설정해서 풀이한다는 아이디어이다.

1. 입력받은 집을 정렬한다. (이분탐색하기 위해)
2. 간격의 최소, 최대를 start와 end로 설정한다.
3. 집들간의 간격이 mid 보다 길다고 하면 최소 간격은 충족했기 때문에 공유기를 설치한다.
4. 집을 모두 돌아다니면서 확인하고 공유기 설치 개수가 요구된 개수를 충족하는지 확인한다.
5. 이렇게 요구를 충족한 간격들 중 최대를 출력한다.

#include <bits/stdc++.h>
using namespace std;
 
int N, C;
vector<int> home;
 
int search(int start, int end){
    int mid, res=0, cnt;
    while(start <= end){
        mid = (start + end) / 2;
 
        int installed = home[0];       
        cnt = 1;
        for (int i=0; i<N; i++){
            if (home[i]-installed >= mid){
                cnt++;
                installed = home[i];
            }
        }
 
        if(cnt >= C){
            res = max(res, mid);
            start = mid+1;
        }
        else end = mid-1;
    }
 
    return res;
}
 
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
 
    int val;
 
    cin >> N >> C;
    
    for(int i=0; i<N; i++){
        cin >> val;
        home.push_back(val);
    }
    sort(home.begin(),home.end());
 
    int min_dist = 1;
    int max_dist = home[N-1]-home[0];
    cout << search(min_dist, max_dist) << '\n';
 
 
    return 0;
}