[c++][algorithm][baekjoon]2110번 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

예제입력1
5 3
1
2
8
4
9

예제출력1
3

 

N : 집의 개수 

C : 공유기 개수 

이후 집의 좌표 

 

N : 3, C: 3

집의 좌표를 먼저 오름차순으로 정렬한다.

1 2 4 8 9

5 3
1
2
8
4
9
i: 1 X[i] : 2 lo:1 hi : 8 mid: 4 start: 1 cnt :1
i: 2 X[i] : 4 lo:1 hi : 8 mid: 4 start: 1 cnt :1
i: 3 X[i] : 8 lo:1 hi : 8 mid: 4 start: 8 cnt :2
i: 4 X[i] : 9 lo:1 hi : 8 mid: 4 start: 8 cnt :2
i: 1 X[i] : 2 lo:1 hi : 3 mid: 2 start: 1 cnt :1
i: 2 X[i] : 4 lo:1 hi : 3 mid: 2 start: 4 cnt :2
i: 3 X[i] : 8 lo:1 hi : 3 mid: 2 start: 8 cnt :3
i: 4 X[i] : 9 lo:1 hi : 3 mid: 2 start: 8 cnt :3
i: 1 X[i] : 2 lo:3 hi : 3 mid: 3 start: 1 cnt :1
i: 2 X[i] : 4 lo:3 hi : 3 mid: 3 start: 4 cnt :2
i: 3 X[i] : 8 lo:3 hi : 3 mid: 3 start: 8 cnt :3
i: 4 X[i] : 9 lo:3 hi : 3 mid: 3 start: 8 cnt :3
3

 

/*[2110]공유기 설치*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int)2e5+10)
int N,C; //집의 개수, 공유기개수 
int X[MAXN];
long long M;

void InputData(){
    cin >> N >> C;
    for(int i =0; i<N; i++){
        cin >> X[i];
    }
}
void Solve(){
    int lo, hi, mid;
    long long sum;
    sort(X,X+N);
    lo = 1;
    hi = X[N-1] - X[0];
    int d = 0;
    int ans = 0;
    while(lo <= hi){
        mid=(lo+hi)/2; 
        int start = X[0];
        int cnt = 1;
        for(int i=1; i<N; i++){
            d = X[i] - start;
            if(mid <= d){
                ++cnt;
                start = X[i];
            }
       cout << "i: " << i << " X[i] : " << X[i] << " lo:" <<  lo  << " hi : " << hi  <<  " mid: " << mid <<  " start: " << start << " cnt :" << cnt  << endl;
         }
        if( cnt >= C){
            ans = mid;
            lo = mid + 1;
        }else{
            hi = mid - 1;
        }

        }
    cout << ans << endl;
}
int main(){
    InputData();
    Solve();
    return 0;
}
/*[2110]공유기 설치*/