백준 2110 - 공유기 설치

1. 문제 정리
  - 집의 수 N개에 공유기의 수는 C개이다.

  - 각 집의 좌표는 x의 배열이며, 각 좌표는 중복되지 않는다.

  - 좌표 하나당 공유기 하나를 설치할 수 있다.

  - 가장 인접한 두 공유기 사이의 거리의 최대값을 구한다.
 
2. 접근
  - 중요한 부분은 두 공유기 사이의 거리의 최대값을 구한다는 점이다.

  - x 좌표 하나하나가 아닌, 인접한 두 x좌표의 간격을 이용하여 이분탐색을 이용하여 문제를 해결한다.
 
3. 풀이

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

int n, c;
int lo = 1;
int hi = 0;
int ans = 0;
vector<int> x;

void bis(){
    int d = 0;
    while(lo <= hi){
        int mid = (lo + hi)/2;
        int cnt = 1;
        int start = x[0];

        for(int i = 1; i < n; i++){
            d = x[i] - start;
            if(mid <= d){
                cnt+=1;
                start = x[i];
            }
        }

        if(cnt >= c){
            ans = mid;
            lo = mid+1;
        }else hi = mid-1;
    }
}

int main(){
    cin >> n >> c;
    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        x.push_back(input);
    }

    sort(x.begin(), x.end());
    lo = 1;
    hi = x.back() - x.front();
    bis();
    cout << ans << '\n';
}

  - vector<int> x : x 좌표들을 저장할 벡터

  - void bis() : 이분탐색을 실행하여 최대값을 구한다. lo에는 1, hi에는 x 좌표의 최대 간격값(가장 끝값 - 가장 앞값)을 설정하고 이분탐색을 실행한다. cnt의 초기값이 1인 이유는 , 검사하는 것은 간격이기 때문에 첫번째 집의 값을 하나 추가해주는 것으로 봐도 무방하다.

d에는 각 간격의 값이 들어가며, d 값이 mid 값보다 크거나 같을 경우 cnt를 1 늘려주고 start값에 x[i]값을 넣어준다

-> cnt를 늘리는 것은 하나의 공유기를 설치하는 것으로 본다. start값을 갱신하는 것은 공유기를 설치하였으니 이후 공유기의 설치를 위해 가장 최근에 설치된 공유기의 위치로 start를 갱신한다.

이후 cnt가 c값 보다 크거나 같다면 간격이 짧다고 볼 수 있으므로 lo 값(하한값)을 올려주고 답을 저장해둔다.

그렇지 않을 경우, 간격이 길어서 c값 만큼 공유기를 두지 못했다고 볼 수 있으므로 hi 값(상한값)을 내려주어 간격을 짧게 만든다.
 
4. 소감

 - 아직은 이분탐색 문제가 어렵게 느껴지는게 사실이다. 특히 이번 문제 같은 경우에는 이분탐색을 공부하기 위해 찾은 문제라 이분탐색으로 접근하였지, 그렇지 않았다면 이분탐색으로 풀 생각도 못 했을 거라 생각한다. 이 문제를 풀기 위해 다른 블로그도 찾아가고 하였지만, 사실 아직 익숙하지 않은 문제 해결 방식이라고 생각한다. 앞으로 더 익숙해지려면 비슷한 문제를 찾아보고, 이분탐색에 대한 이론도 더 공부를 해보아야 하겠다고 생각하였다.