백준 2110번 : 공유기 설치 - binary search , Decide problem - C++

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

2110번: 공유기 설치

1. 문제설명

공유기를 설치해야하는 최대 거리를 구하기 위해

이분 탐색법으로 가장 작은 거리와 가장 먼 거리를 확인하면서

주어진 조건으로 공유기를 설치할 수 있는 지 확인해야 하는 문제이다.

 

binary search를 활용한 Decide problem 문제.

 

 

 

2.문제풀이코드

#include <bits/stdc++.h>
using namespace std;

int n,c;
vector<int> house;


//O(N)
bool decide(int dist){
    int cnt = 1;
    int x = house[0];

    for(int i=1; i<n; i++){
        if(house[i] - x >= dist){
            x = house[i];
            cnt++;
        }
    }
    return cnt >= c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> c;

    for(int i=0; i<n; i++){
        int t;
        cin >> t;
        house.push_back(t);
    }
    //O(NlogN)
    sort(house.begin(), house.end());

    
    int lo = 0;
    int hi = 1e9;

    //O(NlogN)
    while(lo<=hi){
        int mid = (lo+hi)/2;
        if(!decide(mid)){
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }

    cout << hi << '\n';

    return 0;
}

백준 2110번 공유기 설치 C++