[백준] 2110번 - 공유기 설치

백준 2110번 공유기 설치

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

---

코드

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

vector<int> arr;

bool chk(int x, int n, int c){
    int idx = 0;
    
    for(int i=0;i<c-1;i++) {
        int tmp = arr[idx];
        while(tmp+x > arr[idx] && idx < n)
            idx++;
        if(idx==n)
            return false;
    }
    return true;
}

int binary_search(int n, int c){
    int s = 0, e = arr[n-1]-1;
    int mid, ret;
    
    while(s<=e){
        mid = (s+e)/2;
        if(chk(mid,n,c)) {
            ret = mid;
            s = mid+1;
        }
        else
            e = mid-1;
    }
    return ret;
}

int main(){
	int n, c, res;

    cin >> n >> c;
    arr.resize(n);
    for(int i=0;i<n;i++)
	    cin >> arr[i];

    sort(arr.begin(), arr.end());    
    res = binary_search(n,c);
    cout << res;
}

---

풀이

1. 입력받은 수를 정렬
2. 이분 탐색
   • 가장 인접한 두 공유기 사이의 거리(mid)를 탐색
   • mid 값으로 c개의 공유기를 설치할 수 있는지 확인