[자바/Parametric-Search] 백준 2110. 공유기 설치

문제

링크

해석

공유기를 설치하는 거리를 x라고 할 때, x를 이분 탐색으로 구하여 답을 도출할 수 있다.

답을 가정할 때, 특정 구간에서는 해당 답이 거짓이고, 특정 구간에서는 해당 답이 참일 수 있는 경우에는 이분탐색을 통한 답 도출을 하는 "parametric search"를 활용할 수 있다.

이 문제는 공유기 설치를 어느 거리로 해야 최대 거리로 설치할 수 있는지 묻는 문제로, parametric search 문제 중 대표 유형인 "칸막이 설치" 유형이라고 할 수 있다.

로직

기본적으로 이분탐색을 통해 찾는 값이 "가장 가까운 라우터끼리의 거리"이다.

1. 라우터 좌표를 배열에 저장하고 정렬한다.
2. 배열을 순회하면서 누적 거리를 재고, 이분탐색을 통해 설정한 '기준 거리'를 넘어갈 때 routerCnt를 증가시킨다.
3. routerCnt가 C보다 크거나 같으면 routerCnt가 줄어들어야 하는 거니까 left를 갱신한다. 또한, 정답을 갱신한다.(이는 계속 거리가 커질 거라서 최대값 갱신시 무조건 답에 가까워짐) ==> 가장 인근 라우터 간 거리가 '기준 거리'임이 보장된 시나리오 상에서는 설치 라우터가 C개 이상이기만 하면 얼마든지 C 개만 설치할 수 있는 것이므로 if (routerCnt >= C)인 경우에 ansDist를 갱신한다.
4. 모든 경우를 탐색한 뒤, ansDist를 출력한다.

고려할 점

• 이분탐색으로 찾는 mid가 의미하는 것이 "가장 가까운 라우터끼리의 거리(=기준 거리)"이다. 따라서 이를 최대한으로 늘리기 위해 라우터 개수가 C 이상일 때 '기준 거리'를 증가시키는 방향으로 설정한다

/**
 * @author HwangBaco
 * @algorithm parametric search
 * @time O(N * log N) ; 정렬 + 이분탐색 --> 320 ms
 * @memory O(N) ; 정수배열 --> 29428 KB
 *
 * N : 집 개수
 * C : 공유기 개수
 */
public class BOJ_2110_공유기설치 {
    private static int N, C;
    private static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new int[N+1];
        arr[0] = 0;

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        // 거리 이진탐색
        int ans = binarySearch();
        System.out.println(ans);
    }

    private static int binarySearch() {
        int left = 0;
        int right = arr[N];
        int targetDist = 0; // "가장 인접한" 두 라우터 간 거리
        int ansDist = 0;
        while (left <= right) {
            targetDist = (left + right) / 2;
            long curDist = 0;
            int routerCnt = 1; // 첫 번째 집에 설치하고 시작.
            for (int i = 2; i <= N; i++) {
                curDist += arr[i] - arr[i-1];
                if (curDist >= targetDist) {
                    curDist = 0;
                    routerCnt++;
                }
            }

            // 가능한 경우에는 더 늘려서 -> 최대가 되게
            if (routerCnt >= C) {
                left = targetDist + 1;
                ansDist = Math.max(ansDist, targetDist); // 수정 부분
            } else {
                right = targetDist - 1;
            }
        }
        return ansDist;
    }

}