[백준 2110] 알고리즘 58일차 : 공유기 설치

www.acmicpc.net/problem/2110

2110번: 공유기 설치

C++ 이분탐색

지금까지 풀었던 이분탐색 문제랑 비슷한 문젠데 난이도가 조금 높은건 기준정하는 함수에 필요한 계산이 좀 많아서 때문인 것 같다.

 

접근방법

간격을 1부터 가장 좌표값이 큰 값을 범위로 이분탐색한다.

집 좌표값 배열은 정렬해둔다.

간격이 mid일때 공유기를 설치할 수 있는 개수가 C개 이상이면 더 큰 간격에서 이분탐색

C개 미만이면 더 좁은 간격에서 이분탐색

 

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;
int N,C;
int houses[200000];
bool isEnough(long long d){
    int total = 0;
    int a = houses[0];
    for(int i = 1 ; i < N ; i++){
        if(a+d <= houses[i]){
            total++;
            a = houses[i];
        }
    }
    return total+1>=C ? true : false;
}
long long binarySearchMax(long long s, long long e){
    long long mid = 0;
    while(s <= e){
        mid = (s+e)/2;
        if(isEnough(mid)){
            s = mid+1;
        }else{
            e = mid-1;
        }
    }
    return s-1;
}
int main(){
    cin >> N >> C;
    for(int i = 0 ; i < N ; i++){
        cin >> houses[i];
    }
    sort(houses, houses+N);
    cout << binarySearchMax(1, houses[N-1]);   
    return 0;
}