백준 2110번 공유기설치

공유기 설치

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

19272

7629

5581

41.852%

문제

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

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

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

입력

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

출력

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

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, c;
    cin >> n >> c;
    
    vector<int> v(n);
    
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    
    sort(v.begin(), v.end());
    
    int first = 1;
    int end = v[n-1] - v[0];
    
    int ans = 0;
    while (first<=end) {
        int cnt = 1;
        int mid = (first + end) / 2;
        int start = v[0];
        
        for(int i=0; i<n; i++){
            if( v[i] - start >= mid){
                cnt ++;
                start = v[i];
            }
        }
        if(cnt >= c){
            first = mid + 1;
            ans = mid;
        } else if(cnt < c) {
            end = mid - 1;
        }
    }
    cout << ans;
 
    return 0;
}

가장 앞에 있는 집부터 공유기를 설치하면서, 다음 집과의 거리 간격이 현재 간격보다 더 크거나 같으면 공유기를 설치하고 그렇지 못하면 넘어가는 방법으로 문제를 풀었다.