(C++) - 백준(BOJ) 2110번 : 공유기 설치 답

www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제 해석이 좀 난해한 이분탐색 문제였습니다.

 

 

 

풀이방법

* 최대한 공유기를 넓게 c만큼 설치했을 때는 집이 각 공유기가 설치된 위치에 위치하고 있습니다.

* 최대한으로 설치하기 위해서는 첫번째 집에 공유기를 설치하면서 시작하는 것이 좋습니다.

 

 1. 집의 좌표를 오름차순으로 정렬

 2. 첫째 집을 제외한 모든 집의 좌표에 대해 공유기  두 개 사이의 거리가 x이상이 되게 할 수 있다면 답을 x로 갱신, 공유기를 설치

 3-1. 설치된 개수가 c이상이면 공유기 사이의 거리를 늘려서 설치 수를 출여야함

 3-2. 설치된 개수가 c미만이면 공유기 사이의 거리를 줄여 설치 수를 늘려야함

 4. 갱신된 답을 반환 후 출력

Code

#include <iostream>
#include <algorithm>
using namespace std;
    int home[200001];

//공유기 두 개 사이의 거리가 x 이상이 되게 할 수 있는가?
int binarySearch(int n, int c){
    int r = home[n-1];
    int l = 1;
    int ans = 0;
    while(l<=r){
        int cnt = 1;
        int mid = (r+l)/2;
        int start = home[0];
        for(int i = 1; i < n; i++)
            if(home[i] - start >= mid) start = home[i],cnt++;
        if(cnt >= c) ans = mid, l = mid + 1;
        else  r = mid - 1;
    }
    return ans;
}

int main(){
    int n,c;
    cin >> n >> c;
    for(int i = 0; i < n; i++) 
        cin >> home[i];
    sort(home,home + n);
    cout << binarySearch(n,c);
}