공유기 설치 - 백준 2110번

2110번: 공유기 설치

수직선 상의 집 N개의 좌표가 주어졌습니다. 이 집들 사이의 공유기 C 개를 골고루 설치 하여 와이파이를 골고루 이용할 수 있습니다. 공유기는 집의 1개만 설치가 가능하며, 집의 좌표가 주어지고, 공유기의 갯수 C가 주어 졌을 때, 공유기를 설치 할때 가장 인접한 공유기의 거리가 최대가 되는 값을 출력 하시오.

 

1. 접근

1. 집의 범위가 1 ~ 1,000,000,000 으로 매우 큽니다.

2. 여기서 가장 인접한 공유기의 최대 거리를 구해야 합니다.

3. 따라서 최적화 문제(문제의 상황을 만족하는 최소값, 최대값을 구하는 문제) 입니다.

4. 이런 최적화 문제를 결정 문제(Yes or No)로 바꾸어 해결 할 수 있습니다. 따라서 파라메트릭 서치로 접근 합니다.
5. 가장 인접한 공유기의 거리의 범위를 구한다.
6. 집의 좌표를 정렬후,
7. [1] - [0]가 최소 범위가 된다,
8. [마지막 인덱스] - [0]이 최대 범위가 된다.
9. mid = (최소 범위 + 최대 범위) / 2 로 mid 를 구한다.
10. 여기서 mid가 가장 인접한 공유기의 거리가 된다.
11. mid 거리로 첫번째 집부터 설치를 한다.
12. 설치후 제공된 공유기의 갯수 C 보다 작으면 (결정 문제)
13. mid 거리를 좁혀 다시 설치(right = mid - 1)
14. 설치후 제공된 공유기의 갯수가 C 보다 크면 (결정 문제)
15. mid 거리를 늘려 다시 설치(left = mid + 1) 
16. 공유기의 갯수 C와 같을 때까지 설치 하는게 아니고
17. mid의 최소 범위가 최대 범위 보다 크거나 같을때 까지 설치를 진행
18. 최적의 mid 값 반환

 

 

2. Java 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ2110_2 {
    // https://www.acmicpc.net/problem/2110
    // 공유기 설치
    public static void main(String[] args) throws IOException {
        // 집의 개수 N (2 ≤ N ≤ 200,000)
        // 공유기의 개수 C (2 ≤ C ≤ N)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int[] position = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            position[i] = Integer.parseInt(st.nextToken());
        }

        System.out.print(new BOJ2110_2().solution(N, C, position));
    }

    public int solution(int N, int C, int[] position){
        // 집의 좌표를 정렬후,
        // 시간 복잡도 : nlogN
        Arrays.sort(position);

        // [1] - [0]가 최소 범위가 된다,
        // [마지막 인덱스] - [0]이 최대 범위가 된다.
        int left = position[1] - position[0];
        int right = position[N - 1] - position[0];
        int result = 0;

        // mid의 최소 범위가 최대 범위 보다 크거나 같을때 까지 설치를 진행
        // 총 시간 복잡도 : 200,000 x log(200,000)
        // 시간 복잡도 : log 200,000
        while(left <= right) {
            // mid = (최소 범위 + 최대 범위) / 2 로 mid 를 구한다.
            int mid = (left + right) / 2;
            int cnt = 1;
            int prev = position[0];

            // mid 거리로 첫번째 집부터 설치를 한다.
            // 시간 복잡도 : 200,000
            for (int i = 1; i < N; i++) {
                if (position[i] - prev >= mid) {
                    prev = position[i];
                    cnt++;
                }
            }

            if (cnt >= C) { // mid 거리를 좁혀 다시 설치
                left = mid + 1;
                result = mid;
            } else {        // mid 거리를 늘려 다시 설치
                right = mid - 1;
            }
        }
        return result;
    }
}

 

 

3. 진행 과정

파라메트릭 서치를 처음 접하시는 분들은 다소 헷갈릴수 있습니다. 저도 그랬거든요. 그래서 그림으로 표현해 보며 아래 와 같습니다.

 

먼저, 공유기 간격을 mid 라고 했을때, 최소 범위 : left, 최대 범위 : right를 구합니다.

left : position[1] - position[0] 

right : position[n - 1] - position[0]

이렇게 공유기 mid의 범위를 구하고, 가운데 값 mid를 공유기의 간격으로 가정하고, 처음 집 부터 설치를 진행 합니다.

position[0] 의 설치 후, mid : 4 만큼 뒤의 값인 좌표가 5인 곳의 설치를 합니다. 하지만 좌표가 5인 곳은 집이 없으르모 5 바로 뒤에 있는, 좌표 8인 곳에 설치 합니다. 따라서, mid가 4 인 경우 공유기 2개 밖이 설치 못하므로, 공유기 간격 범위를 좁혀 줍니다.

 

 

공유기 간격 범위를 좁혀 주기 위해서 right = mid - 1로 범위를 좁혀주어 탐색 합니다. 이 범위를 좁혀주는 과정이 이진 탐색(Binary Search)와 흡사 합니다. 따라서 시간 복잡도도 O(logN)으로 탐색 할수 있습니다. right의 범위가 좁혀졌으니 mid 값도 다시 계산 하면, 2가 됩니다. 다시 간격 2로 집의 설치를 진행 합니다. 먼저, 좌표 1인 집의 설치 후, 좌표 3의 설치를 해야 하는데, 집이 없으므로 좌표 4의 설치 합니다. 그리고 좌표 6의 설치 해야 하는데, 집이 없으므로 8의 설치를 진행 합니다. 공유기를 원하는 갯수 3개 만큼 설치를 했지만, 우리가 아직 탐색 하지 않은 범위가 있습니다. mid 가 2 ~ 4 사이의 있는 3의 값을 탐색 하지 않았습니다. 문제는 최적화를 구해야 하므로, 가장 인접한 공유기 간격의 최대값이므로, 3 또한 탐색을 실시해 주어야 합니다.

 

 

left = mid + 1 로 범위를 또 좁혀 줍니다. 그럼 mid 는 3이 되고, 집의 설치를 진행 하면, 좌표 1, 좌표 4, 좌표 8의 설치 할 수 있습니다. 더 탐색할 수 있는 범위가 없으므로 mid 값 3을 반환 합니다.