[백준] 2110번: 공유기 설치

 

이분 탐색 문제이다.

 

 

 

 

 

 

 

 

 

 

처음 생각했던 접근방식

 

공유기를 최대한 고르게 분포해야 하는 문제이므로,

공유기를 무조건 2개 배치해야하니 양쪽 끝에 있는 집에 하나씩 놓는 방법을 생각했다.

 

예를 들어, 집의 위치가 1,2,3, ... ,10 까지 존재할 때,

1번 공유기가 1번, 2번 공유기가 10번에 놓여진다.

그러나 그 다음 3번 공유기를 고르게 분포하게끔 배치하려면 최대한 가운데 쪽 (5번이나 6번)에 위치하게 배치해야했는데,

만약 놓아야 하는 공유기가 4개일 경우, 3번 공유기를 5번이나 6번에 배치하게 되면,

4번 공유기를 아무리 잘 놔도 인접한 최대 거리는 2가 된다.  

만약 3번 공유기를 4번에 놓는다면 4번 고유기가 7번에 놓여지고, 그렇다면 공유기의 위치가 1,4,7,10이 되어 거리가 3이 된다.

 

즉, 양쪽에 배치해놓고 공유기를 최대한 가운데에 배치하는 것은 공유기가 4개 이상일 때 좋은 방법이 아니였다.

이후로 마땅한 해결책이 생각이 나지 않았는데, 맨 처음 두개의 공유기를 양쪽에 무조건 배치해야 한다라는 고정관념 때문이었다.

 

 

 

 

 

 

 

 

합당한 접근방식

 

위의 문제 예시에서도 드러나듯, 공유기가 무조건 양쪽 끝에 있을 필요는 없다.

양쪽에 배치하는 것이 틀린 것은 아니지만, 그것에 너무 신경쓰다보면 올바른 접근방식을 생각해내지 못하게 하는 것 같다.

 

다만 맨 처음 공유기는 맨 처음 집의 좌표에 배치되어야 한다. 

이 후의 공유기의 배치는 결국 공평하게 배치될 수 있는 "간격"에 따라서 배치된다고 볼 수 있다.

 

즉, 이 간격을 이분 탐색으로 찾을 수 있다.

일반적인 이분 탐색은 인덱스 기반이지만, 간격을 찾는 데 사용되므로 간격을 기준으로 이분 탐색을 진행한다.

 

 

1. 최소 간격을 1로 두고, 최대 간격을 양쪽 끝 집의 거리라고 둘 수 있다.
2. 가장 공평하게 공유기를 둘 수 있는 간격을 정한다 (avgDist = (minDist+maxDist)/2)
3. 최근에 놓은 공유기에서 avgDist보다 멀리 공유기를 배치하는 경우, 공유기를 놓은 개수를 카운트 한다.
4. 만약 공유기의 개수가 놓아야하는 개수보다 많은 경우, 간격이 좁았다는 의미이므로 간격을 늘린다. (minDist = avgDist+1)
5. 만약 공유기의 개수가 놓아야하는 개수보다 적은 경우, 간격이 넓었다는 의미이므로 간격을 줄인다. (maxDist = avgDist-1)

 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){
 
    int N, C;
    cin >> N >> C;
    vector<int> pos(N);
 
    for(int i=0; i<N; i++){
        cin >> pos[i];
    }
 
    sort(pos.begin(), pos.end());
 
 
    int minDist = 1;
    int maxDist = pos[N-1]-pos[0];
 
 
    int numRouters, avgDist, recentRouter;
    int ret = 0;
    while(minDist <= maxDist){
        numRouters = 1;
        avgDist = (minDist + maxDist)/2;
        recentRouter = pos[0];
 
        for(int i=1; i<N; i++){
            if(pos[i]-recentRouter >= avgDist){
                recentRouter = pos[i];
                numRouters++;
            }
        }
 
        if(numRouters > C){ //라우터를 더 많이 심은경우->최소 간격을 늘리자
            minDist = avgDist+1;
            ret = max(ret, avgDist);
        }else if(numRouters < C){ //라우터를 더 적게 심은경우->최대 간격을 줄이자
            maxDist = avgDist-1;
        }else{ //딱 맞게 심은경우->계속 진행
            minDist = avgDist+1;
            ret = max(ret, avgDist);
        }
    }
    cout << ret;
 
    return 0;
}

 

이분 탐색의 개념 자체는 어렵지 않지만, 문제에 활용될 때 상당히 까다로운 느낌을 받았다.

이 개념을 이렇게 문제에 활용한다는 것이 상당히 놀라웠고, 다음에는 잘 풀 수 있도록 개념을 다시 한번 정리해야겠다 :)