백준 #2110 / 공유기 설치

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2725	1386	1017	49.829%

문제

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

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

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

입력

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

출력

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

---

진짜 감이 하나도 안왔었다... 처음에 든 생각은 "와이파이 공유기 설치하면 어디까지 닿는데??" 였다.

"아니 와이파이가 어디까지 닿는지 알아야 설치를 하든지 말든지 하지..."

근데 곰곰히 생각해보니까... 이거에 대한 언급이 1도 없다는건 상관이 없다는 것을 의미하는게 아닐까 싶었다.

그냥 닿든지 말든지... 설치만 하면 된다 이 말이다. 차라리 김장독을 묻는다고 했으면 생각이라도 잘 날텐데 ㅜㅜㅠ

[How To Solve?]

- 시작점에는 무조건 공유기를 설치한다는 전제를 깔고 가야한다.

- 그 다음, 시작점과 가장 멀리 떨어진 집과의 거리를 MAX로 잡는다.

- 1부터 MAX 사이에서 적정거리를 찾아나선다.

- mid = (1+MAX) / 2 로 두고 이 간격으로 공유기를 설치했을 때, 결과가 나뉘는데 어떻게 나뉘냐면

- 공유기가 예정보다 많이 설치된 경우와 덜 설치되거나 딱 맞게 설치된 경우.

- 전자의 경우, 거리를 무조건 줄여야한다. 그래야 공유기를 알맞게 설치할 수 있으니까. right = mid-1

- 후자의 경우, 거리를 늘리는 대신 mid값을 MAX_len에 갱신해준다. 어차피 공유기 설치 횟수가 가능 횟수와 같은 경우, 최대값이 마지막에 갱신되므로 대소비교는 해줄 필요가 없다.

[Code]

#include<iostream>
#include<algorithm>
#define MAX_SIZE 200001
using namespace std;
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
 
    int N,C,MAX=0;
    cin >> N >> C;
 
    int arr[MAX_SIZE] = { 0, };
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        MAX = MAX < arr[i] ? arr[i] : MAX;
    }
    sort(arr, arr + N);    // 정렬
 
    int left = 1;
    int right = MAX;
    int MAX_len = 0;
 
    // 이분 탐색으로 가장 긴 거리를 구한다.
    while (left <= right) {
        int mid = (left + right) / 2;    // 중간값으로 지정
        int cnt = 1;    // 0번째에는 공유기 설치했다고 가정하고 시작
        int start = arr[0];    // 0에 공유기 설치했으니까 시작점으로 두고, mid보다 크거나 같은 최초지점 찾으면, 그 점에 공유기 설치.
 
        for (int i = 1; i < N; i++)
        {
            if (arr[i] - start >= mid) {
                start = arr[i];
                cnt++;
            }
        }
        // 위에서 공유기 갯수 모두 파악됨.
 
        if (cnt >= C)    // 설치된 공유기 갯수가 설치 가능 횟수보다 크거나 같으면
        {
            MAX_len = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    printf("%d\n", MAX_len);
}