백준 2110 공유기 설치 - 이분탐색 C++

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

2110번: 공유기 설치

 

main 함수의 이분탐색 방식은 똑같고,

어떤 interval을 두고 공유기를 설치할수 있냐 없냐를 판단 하는 여부가

조금 까다로운 부분이지 않았나 싶었다.

13번째 줄에 current_x를 current_x+interval로 두지 않고 x[i]로 두어야 하는 부분을 조심하자.

어떤 인터벌을 두고 공유기를 n개 이상 설치하면 true 아닐 시 false이다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int n,c;
int x[200001];
 
bool ispossible(int interval){
    int current_x = x[0];
    int housenum=1;
    for(int i=1; i<n; i++){
        if(x[i]>=current_x+interval){
            current_x=x[i];
            housenum++;
        }
    }
    if(housenum>=c)
        return true;
    return false;
}
 
int main(void){
    cin>>n>>c;
    int Min,Max=0;
    for(int i=0; i<n; i++){
        cin>>x[i];
        Min = min(Min,x[i]);
        Max = max(Max,x[i]);
    }
    //x 정렬하고
    sort(x,x+n);
    int high = (Max-Min)/(c-1);
    int low=1;
    int answer=0;
    while(low<=high){
        int mid = (high+low)/2;
        if(ispossible(mid)){
            if(answer<mid)
                answer=mid;
            low = mid + 1;
        }
        else{
            high = mid -1;
        }
    }
    cout<<answer;
    //ispossible때려가면서 이분탐색
 
}