[알고리즘 풀이 분석] BOJ 2110 공유기 설치

오늘 풀어본 두번째 문제는 BOJ 2110 공유기 설치 이다!
스스로 이분탐색에 약한편이라 생각해서 오랜만에 이분탐색 문제를 한번 풀어보았다. 역시나 어려웠다,,, 다른 포스팅의 도움을 살짝 받아 해결했다!

늘 고민인게, 모르면 끝까지 고민을 해야 하는건지,,
어느 선까지 고민하고 해결책을 찾아봐 해결해야 하는 건지 고민이다.

누구는 어차피 코딩테스트에서 오래 고민하는건 의미가 없으니 오래 고민해서 안되는거면 그럴 필요가 없다고 하긴 하는데,,

BOJ 2110 공유기 설치

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입출력

나의 풀이

이분 탐색 문제임을 알고 시작했기 때문에 어떤 기준점을 잡아서 그 중간 값을 조절해 가면서 풀어야 하는 문제일거라고 생각할 수 있었다.

구하고자 하는 '가장 인접한 두 공유기 사이의 거리' 를 최솟값, 최댓값 사이에서 조절해 가면서 적당한 거리를 찾아가는데 그게 적당한지, 아닌지를 판단하는 기준을 떠올리기가 어려웠던 것 같다.

관련 포스팅을 좀 찾아본 결과 간격을 x 로 해서 주어진 C 개의 공유기를 모두 설치할 수 있으면 해당 x 는 정답으로 가능한 값에 속하는 것이었다.

이부분을 떠올릴 수 있었으면 100% 내 힘으로 푼 문제가 될텐데,, 아쉽지만,, 더 연습하지 뭐!!

알고리즘 동작 방식은 다음과 같다.

• 입력으로 받은 집 위치를 기반으로 가능한 최소 공유기 사이 거리 = 1, 최대 공유기 사이 거리 = 마지막 집 - 첫 집 를 설정한다.
• mid = (최소 공유기 사이 거리 + 최대 공유기 사이 거리)/2 를 기준으로 C개의 공유기를 설치 할 수 있는지 확인한다.
• 현재집 + mid 의 위치보다 크거나 같은 곳에 있는 첫번째 집에 두번째 공유기 설치, 현재 집 = 두번째 공유기 위치 로 변경
• 반복하며 주어진 집 범위 내에서 C 개의 공유기를 모두 설치 할 수 있는지 확인
• C 개 보다 적게 설치했다면 최대 공유기 사이 거리 값 조정 (간격 좁히기)
• C 개 설치 했다면 현재의 mid 값 저장
• C 개 이상 설치했다면 최소 공유기 사이 거리 조정 (간격 늘리기)

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

// BOJ 2110 공유기 설치, Binary Search, 실버 1
using namespace std;

int findGap(vector<int> house, int N, int C){
    int answer;
    int minGap = 1, maxGap = house[house.size()-1] - house[0];
    int mid;

    while (minGap <= maxGap){
        mid = (minGap + maxGap)/2;
        int router = 1;  // 설치 공유기 수 
        int last = 0, next = 1;  // last = 직전 공유기 위치, next = 다음 공유기 위치 탐색 

        while (next<N && router<C){
            if (house[next]>= house[last]+mid){
                router++;
                last = next;
                next = last+1;
            }else{
                next++;
            }
        }

        if (router < C){  // 공유기 다 설치 못했으면 간격을 줄이기 
            maxGap = mid-1;
        }else if (router == C){  // 공유기 다 설치 했으면 임시 정답 저장, 간격 늘리기 
            answer = mid;
            minGap = mid+1;
        }else{  // 간격 늘리기 
            minGap = mid+1;
        }
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, C;
    cin>>N>>C;

    vector<int> house(N, 0);
    for (int i = 0; i < N; ++i) {
        cin>>house[i];
    }

    sort(house.begin(), house.end());

    int answer = findGap(house, N, C);

    cout<<answer;

    return 0;
}

[파이썬] BOJ 2110번 - 공유기 설치