[C++] BAEKJOON 2110 공유기 설치

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

2110번: 공유기 설치

이분탐색 을 활용하여 해결하였습니다.

가장 인접한 두 공유기 사이의 최대 거리 를 구하는 문제입니다. 이 거리를 answer 라고 하면 answer 값을 구해주기 위해서 이분탐색으로 찾아갑니다. 최소값은 1 이므로 left 는 1로 초기화하고, 최대값은 양 쪽 끝의 공유기 거리 이므로 right 는 이 값으로 초기화 해줍니다. 가장 인접한 두 공유기 사이의 거리를 mid 로 결정하였을 때는 놓을 수 있는 공유기의 개수, count 를 계산해줍니다. count 를 확인하기 위해서는 마지막에 공유기를 설치한 집부터의 거리가 mid 보다 크면 공유기를 설치하고 개수를 증가해줍니다. 놓을 수 있는 공유기의 개수 count 가 놓아야하는 공유기의 개수 C 보다 크다면 mid 를 증가시키고 그렇지 않으면 mid 를 감소시켜면서 answer를 찾게 됩니다.

#include <iostream>
#include <algorithm>

using namespace std;

int home[200000];

int main(){
    int N,C;
    cin >> N >> C;
    
    for (int i=0;i<N;i++){
        cin >> home[i];
    }
    
    sort(home, home+N);
    
    int answer = 0;
    
    long long left = 1;
    // 두 공유기 사이의 최대 거리는 맨 뒤와 맨 앞의 차이
    long long right= home[N-1]-home[0];
    
    while (left<=right){
        long long mid = (left+right)/2;
        
        int count=1;
        
        int start = home[0];
        
        for (int i=1;i<N;i++){
            int distance = home[i] - start;
            if (distance >= mid){
                count++;
                start = home[i];
            }
        }
        
        if (count>=C){
            left = mid+1;
            answer = mid;
        }
        else {
            right = mid-1;
        }
    }
    cout << answer << "\n";
}