Easy is Perfect

[백준] 2110번 C/C++ 풀이 _ 공유기

  • melonicedlatte
  • Jul 29, 2018


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

공유기 설치

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB33661705127450.356%

문제

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

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

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

입력

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

출력

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

예제 입력 1 

5 3
1
2
8
4
9

예제 출력 1 

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

풀이 

이 문제는 결론부터 말하자면 '이진 탐색'을 써야 합니다.


정답이 될 수 있는 최소값은 1, 최대값은 위의 그림처럼 시작과 끝 값 간의 차이가 됩니다.


위에는 간격이 3일 때의 예시입니다. 

한 단계의 탐색 방법은 가장 앞에 있는 집부터 공유기를 설치하면서, 다음 집으로 넘어 가면서 거리 간격이 현재 간격보다 더 크면
공유기를 설치하고 그렇지 못하면 넘어가는 방법입니다. (소스코드를 참조하면 더 이해가 쉽습니다.)

이렇게 설치한 공유기가 C 와 같거나 크면 해당 위치에 공유기를 설치하고 간격으로 넘어갑니다.  

하지만 최소값부터 끝값까지 탐색하면 O(N2) 의 복잡도를 가집니다. 

복잡도를 줄이기 위하여 이진탐색을 이용해야 합니다.
공유기의 거리를 이진 탐색을 이용하여, left와 right를 변경하면서 진행하면 됩니다.

소스코드를 보는 것이 이해를 더 빠르게 도울 수 있을 것입니다. 

소스코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable : 4996)
 
using namespace std;
 
int main() {
    // init
    vector<int> gong_u;
    int N, C;
    cin >> N >> C;
 
    // 공유기에 값 넣기
    for (int n_idx = 0; n_idx < N; n_idx++) {
        int sub;
        scanf("%d", &sub);
        gong_u.push_back(sub);
    }
 
    // 좌표 순서대로 정렬 
    sort(gong_u.begin(), gong_u.end());
 
    // 이진 탐색을 이용하여 존재할 수 있는 간격의 값을 찾는다.
    // 간격의 값은 최대 좌표의 시작점과 끝점의 값의 차이이다. 
    int left = gong_u.front();
    int right = gong_u.back();
    int answer_num = -1;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        int before_set_index = 0;
        int set_num = 1;
 
        // 하나하나 건너 뛰면서 공유기의 값이 현재 값의 mid 이상인 경우에만 설치 가능하다
        for (int n_idx = 1; n_idx < N; n_idx++) {
 
            // 현재 위치와 직전 설치한 공유기의 위치의 간격이 mid 보다 크다면
            if (gong_u.at(n_idx) - gong_u.at(before_set_index) >= mid) {
                before_set_index = n_idx;
                set_num++; 
            } 
        }
        
        // 모든 인덱스를 확인하면 갯수가 입력받은 C보다 큰지 확인한다. 
        // C 보다 크면 현재의 최대값이 되고, left를 변경하여 더 큰 값을 탐색하고 반대인 경우 right 를 변경
        if (set_num >= C) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
 
        // 현재의 설치 대수보다 더 크면 정답을 교체한다. 
        if (answer_num < mid && set_num >= C)
            answer_num = mid;
 
    }
 
    cout << answer_num;
 
    return 0; 
}
cs




Search