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

<문제 링크> 

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

1450번: 냅색문제

<알고리즘 분류> 

 - 이분 탐색(Binary Search) 

<풀이> 

이 문제를 풀기 전에 파악해야 하는 점은, 

문제의 조건(가장 인접한 두 공유기 사이의 최대 거리)을 구하는 데에 있어서, "첫 번째 공유기"는 무조건 포함한다는 것이다. 

또한, 우리가 Focus해야 하는 부분은 "간격"이다. (공유기의 위치가 아니다.) 

예제를 예로 들어 보자. 

[1, 2, 4, 8, 9] 에서, 공유기 2개만 사용한다고 가정했을 때, 공유기 2개의 최대 간격은 8이다. 최소 간격은 1이다. 

결국 공유기 몇 개를 사용하던지 간에, 이 문제의 답은 1과 8 사이에 존재하는 것이다. 

여기까지 이해가 됐다면, 이제 그림을 보자. 

 

<코드>

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

int N, C; //N : 집의개수, C: 
vector <int> router; // 집 저장

int ShareCount(int mid){

    int prev = router[0];
    int count = 1;
    
    for(int i=1; i<N; i++){
        if (router[i] - prev >= mid){
            count++;
            prev = router[i];
        }
    }

    return count;
}
int main(){
    cin >> N >> C;
    for (int i=0; i<N; i++){
        int x;
        cin >> x;
        router.push_back(x);
    }
    int ans;
    sort(router.begin(), router.end());

    int l_gap = 1; 
    int r_gap = router[N-1];

    while(l_gap <= r_gap){
        int mid_gap = (l_gap + r_gap) / 2;

        if(ShareCount(mid_gap) >= C){
            ans = mid_gap;
            cout << "지금" <<ans << "\n";
            l_gap = mid_gap+1;
        }
        else{
            r_gap = mid_gap - 1;
        }
    }

    cout << ans;

}

 

이분 탐색 문제들이 그동안 나에게 조금 어렵게 느껴졌던 듯하다. 개강 전까지 이분탐색 문제들(응용+심화문제)을 풀어봐서 이분탐색에 익숙해져야겠다.