Algorithm) 백준 2110 공유기 설치 c++

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

2110번: 공유기 설치

 

이분 탐색 문제입니다

 

입력으로 주어지는 최대 집 개수가 20만개이므로 일반적인 방법으로는 시간초과가 날 것이기에 이분탐색으로 접근해봤습니다

 

우선 집 좌표의 입력이 오름차순으로 주어지지 않으므로 정렬한 후 

lo에는 최소 거리 1

hi에는 최대 거리인 마지막 집 - 처음 집을 넣어주고 이분탐색을 시작합니다.

 

이분탐색 값은 가장 인접한 공유기 사이의 거리입니다. 

우선 첫번째 집에 공유기 한대를 설치한 후 

for문을 돌면서 현재 좌표 - 이전 공유기 설치 좌표를 계산한 값이 mid보다 크거나 같으면 공유기를 설치해도 가장 인접한 공유기 사이의 거리에 영향을 미치지 않으므로 공유기를 설치해줍니다.

모두 탐색을 완료하고  설치한 공유기 개수가 c보다 크거나 같으면 그 값을 저장해줍니다(ans)

 

c와 같을때만 저장하는게 아니라 c보다 크거나 같을때 ans를 update하는 이유는 

4 3 

1

3

5

7 
이 예시를 살펴보면 알 수 있습니다

이 예제의 답은 2인데 count==c일때만 ans를 업데이트하면 답은 1이 나옵니다  

mid가 2일때 count는 4가 되어서 ans에 값을 저장하지 못하기 때문입니다

 

그래서 이 문제는 N개를 설치했을때 가장 인접한 두 공유기 사이의 거리를 최대로 하는 것 보다는

N개 이상을 설치했을때 가장 인접한 두 공유기 사이의 거리를 최대로 하는 경우를 찾는다고 보는게 이해하기 쉽습니다

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

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

    int n,c;
    cin>>n>>c;
    vector<int> house;
    int ans;
    for(int i=0; i<n; i++) {
        int num;
        cin>>num;
        house.push_back(num);
    }
    sort(house.begin(), house.end());
    int lo = 1;
    int hi = house[n-1] - house[0];
    int mid;
    while(lo <= hi) {
        mid = (lo + hi) / 2;
        int prev = house[0];
        int count = 1;
        for(int i=1; i<n; i++) {
            if(house[i] - prev >= mid) {
                count++;
                prev = house[i];
            }
        }
        if(count < c) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
            ans = mid;
        }
    }
    cout<<ans;
}