백준 - 2110 공유기 설치(Java)

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

2110번: 공유기 설치

 

파라매트릭 서치(Parametric Search) 방법입니다.

파라매트릭 서치는 '최적화 문제를 결정 문제로 바꾸는'방법입니다.

이 것은 이분탐색과 매우 유사한데, https://www.crocus.co.kr/1000에 매우 잘 설명이 되어 있느니 꼭 읽어보시기 바랍니다.

 

이 문제에 파라매트릭 서치를 적용하면 다음과 같이 문제를 변형해서 해석할 수 있습니다.

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

-> 첫 번째 집을 x1이고 마지막 집을 x2라 했을 때, 거리(x2-x1) 부터 거리를 절반씩 줄이며 공유기를 C개 만큼 설치할 수 있는가?

 

변형된 문제를 다시 읽어보면 거리를 절반씩 줄이는 이분탐색을 통해 각 거리마다 설치 가능한 공유기 개수를 알 수 있고, 이 중 최대를 찾으면 됩니다.이 때 사용된 이분탐색은 Upper-Bound입니다.

 

[구현 코드]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int n, c;
    private static int[] home;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        c = Integer.parseInt(stz.nextToken());

        home = new int[n];

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

        // 정렬
        Arrays.sort(home);

        // 최소 1만큼의 거리는 설치할 수 있음
        int lo = 1;
        // 최대 끝에서 끝까지의 거리까지 설치할 수 있음(공유기가 2개일 때)
        int hi = home[n-1] + home[0];

        // 설치 가능한 거리를 줄여가면서 최대를 찾음
        // UpperBound로 찾고자 하는 값의 초과를 찾음
        while (lo<hi){
            int mid = (lo+hi)/2;

            if(canInstall(mid) < c){
                // 현재 거리만큼 설치를 하지 못하면
                hi = mid;
            }else{
                // 현재 거리 이상으로 설치할 수 있기 때문에 설치 범위를 늘림
                lo = mid +1;
            }
        }

        // 초과이기 때문에 1을 뺌
        bw.write(String.valueOf(lo-1));

        bw.flush();
        bw.close();
        br.close();
    }

    private static int canInstall(int dis) {
        // 첫 번째 집은 무조건 설치
        int cnt = 1;
        // 지난 공유기가 설치된 집 위치
        int lastInstalledHome = home[0];

        for(int i=1; i<n; i++){
            // 현재 거리 이상으로 설치할 수 있으면
            if(home[i] - lastInstalledHome >= dis){
                cnt++;
                lastInstalledHome = home[i];
            }
        }
        return cnt;
    }
}