[백준 2110] - 공유기 설치 (JAVA) + Parametric search 알고리즘

[문제]

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

2110번: 공유기 설치

---

 

[문제풀이 전]

 

이코테책의 Q29번 문제이기도 합니다. 해당 문제를 풀 때는 단순 이분 탐색을 사용해서 푸는 줄 알고 있었는데, 이것을 응용해서 푸는 것을 Parametric Search라는 기법이 있는 것을 알게 되었습니다.

 

 

 Parametric Search 정의

- 조합 최적화를 위한 알고리즘의 설계 및 분석에서 파라매트릭서치는 결정 알고리즘을 최적화 알고리즘으로 변환하기 위해 Nimrod Megiddo의해 발명된 기술입니다. computational geometry에서 최적화 문제를 해결하는데 자주 사용됩니다.

참고 - 위키백과

 

 

Parametric Search는 Binary Search를 응용한 것입니다. 주로 최솟값, 최댓값을 이분탐색으로 찾을 때 사용됩니다.

예를들어 어떤 문제에서 조건을 만족하는 최솟값을 구하라고 가정합니다. 문제의 정답이 ans이고, ans 이상의 모든 값은 조건을 만족한다면 정답을 가정하고 해당 값이 조건을 만족하는지 확인해서 문제를 해결 할 수 있습니다.

 

1	2	3	4	5	6	7	8	9	10
X	X	X	O	O	O	O	O	O	O

 

1. 탐색을 하는 위치(인덱스)가 가능 한지 불가능 한지 판단합니다.

2-1. 만약 가능(O) 하다면 더 작은 값으로 시도(high 를 땡겨옵니다)

2-2. 만약 불가능(X) 면 더 큰값으로 시도(low를 땡겨옵니다)

3. 이와같은 탐색을 반복하는 것이 Parametric Search 입니다.

 

1번에서 가능/불가능의 여부는 결정함수 를 만들어야 합니다. pos(int limit) 이러한 형태로 가장한 값을 넘겨줘서 가능/불가능을 판단하여 return 하도록 설계합니다.

시간 복잡도는 O(T(n)logK) 가 됩니다. (T(n) = 결정함수의 시간복잡도, K = 탐색의 범위)

 

문제를 풀 때 이분탐색으로 최소, 최대 값을 찾고자 해야 하는 상황일 때, 그 값을 위해 특정 변수의 범위를 계속해서 좁혀 답을 찾는 방법입니다.

 

---

[문제풀이] 

 

우선 입력으로 주어진 집의 좌표를 나타내는 x 의 범위에서 힌트를 얻을 수 있습니다. 10억이라는 큰 수로 단순 for문으로는 해결할 수 없다는 사실을 알 수 있습니다. 또 가장 인접한 두 공유기 사이의 '거리'를 가능한 크게 하여 설치하려기 때문에 특정 '거리'마다 공유기를 설치할 때 설치 된 공유기의 수를 알 수 있습니다. 그래서 logN의 방법인 이분 탐색을 N번 반복하는 Parametric Search를 활용하여 풀 수 있습니다. C개의 공유기를 설치했을 때 만족하는 최소거리 범위중 가장 큰 경우를 출력하면 됩니다.

 

최소거리를 구할 때는 직전에 설치한 집과 현재 집과의 거리 기준으로 판단해야 합니다. 최소 거리가 가질 수 있는 최솟값은 1이고, 최대 거리가 가질 수 있는 최댓값은 첫번째 집과 가장 뒤에 집의 거리의 차입니다. 위의 정보를 토대로 코드를 작성해보겠습니다. 

 

 

---

 

[소스코드] 

 

import java.util.*;
import java.io.*;

public class Main {

    static int[] house;
    public static void main(String[] args) throws IOException {
        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());
        house = new int[n];

        for (int i = 0; i < n; i++) {
            house[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(house);

        int low = 1;
        int high = house[n - 1] - house[0];
        int ans = 0;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (wifi(mid) < c) {
                high = mid - 1;
            }else{
                ans = mid;
                low = mid + 1;
            }
        }

        System.out.println(ans);

    }

    private static int wifi(int dist) {
        int count = 1;
        int prevLocate = house[0]; //직전 위치

        for (int i = 1; i < house.length; i++) {
            int nowLocate = house[i];

            if (nowLocate - prevLocate >= dist) {
                count++;
                prevLocate = nowLocate;
            }
        }

        return count;
    }
}