[백준 2110] 공유기 설치

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

나무자르기 문제를 풀고 이진탐색을 좀 집중공략할 필요가 있다고 생각이 들어서 당분간 이진탐색 문제를 집중적으로 풀려고 한다.
이 문제의 경우 아까와 비슷한 방식으로 이진탐색 > n번 탐색 의 알고리즘을 가진다.

풀이 방법

1. 집의 좌표를 정렬한다.
2. 좌표의 간격의 최댓값과 최솟값을 구한다.
   • 최소 간격: 1
   • 최대 간격: 좌표가 제일 큰 집 - 제일 작은 집
3. 간격을 이분탐색하며 적절한 간격을 구한다.
   • 만약 집 간의 간격이 이분탐색의 mid값보다 크면 cnt++
   • cnt가 m보다 많다면 result = mid(현재까지의 최대 간격)
     + min값을 mid로 설정하고 더 큰 간격이 있는지 이진탐색 시작
   • cnt가 m보다 작다면 max=mid로 설정하고 더 좁은 간격에서 m만큼의 공유기가 설치된 간격을 찾음

시간 복잡도

이진탐색($logm$) * n
=$O(nlogn)$

구현

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    int n;
    int m;
    int house[200000];

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> house[i];
    }
    sort(house, house + n);
    
    int min = 1, max = house[n-1] - house[0];
    int result = 0;
    
    while (min <= max) {
        int mid = (min + max) / 2;
        int current = house[0];
        int cnt = 1; 
        
        for(int i = 1; i < n; i++){
            if(house[i] - current >= mid) {
                cnt++;
                current = house[i];
            }
        }
        
        if(cnt >= m){
            result = mid;
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }
    
    cout << result;
    return 0;
}