boj 2110 공유기 설치

www.acmicpc.net/problem/2110

2110번: 공유기 설치

M개의 공유기를 놓을 수 있는 최대한의 간격을 구하는 문제입니다.

최대한의 간격은 최적화된 정답을 구하는 것이므로 파라매트릭 서치로 해결합니다.

 

우선 이분탐색을 쓰기 위해 입력받은 위치정보를 정렬합니다.

탐색 범위는 간격이며, (1 ~ list[N] - list[1])의 범위에서 탐색합니다.

 

간격 m에서 공유기를 M개 이상 놓을 수 있는지 확인합니다.

놓을 수 있으면 true, 아니면 false를 리턴합니다.

 

solve함수의 리턴 값이 true면 ans에 현재 간격을 저장하고 (m + 1 ~ r) 범위를 탐색합니다.

solve함수의 리턴 값이 false면 (s ~ m - 1) 범위를 탐색합니다.

 

모든 간격을 확인 하였을 때 지금까지 구했던 최적의 간격을 출력합니다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int list[200001];
int N, M;
 
bool solve(int length) {
    int pre = list[1];
    int cnt = 1;
    for (int i = 2; i <= N; i++) {
        if (list[i] - pre >= length) {
            cnt++;
            pre = list[i];
        }
    }
 
    if (cnt >= M) return true;
    else return false;
}
 
int binarySearch(int l, int r) {
    int ans = 0;
 
    while (l <= r) {
        int m = (l + r) / 2;
        if (solve(m)) {
            ans = m;
            l = m + 1;
        }
        else r = m - 1;
    }
 
    return ans;
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    sort(list + 1, list + 1 + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << binarySearch(1, list[N] - list[1]) << '\n';
 
    return 0;
}