[Algorithm] Parametric Search(with. Baekjoon 2110)

📢

Binary Search를 이용한 최적값 탐색 기법

• 연속적이거나 이산적인 값의 집합에서 최적값 X를 찾는 문제
  • X를 경계로 조건을 만족하는 집합과 답이 될 수 없는 집합을 판정할 수 있을 때
  • 추정값 A에 대한 판정을 반복해 X를 찾는 방법

모든 추정값 X를 모두 확인하지 않아도 최적값 X를 기준으로 판정결과가 나눠진다면 Binary Search를 적용해볼 수 있음.

예시 문제(백준 2110, 공유기 설치)

• 시간복잡도 - O(N * log(maxDistance))

public class Main {
    static int N;
    static int C;
    static long[] point;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 초기화
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);

        point = new long[N];
        for (int i = 0; i < N; i++) {
            point[i] = Integer.parseInt(br.readLine());
        }

        // 정렬
        Arrays.sort(point);

        System.out.println(getMaxDistance(point));
    }

    private static long getMaxDistance(long[] point) {
        long l = 1, r = point[N-1] - point[0];
        long ans = 0;
        
        while(l <= r) {
            long m = (l + r) / 2;
            
            if (isInstallable(m)) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }

    private static boolean isInstallable(long m) {
        long lastInstalled = point[0];
        int count = 1;
        
        for(int i = 1; i < N; i++) {
            if (point[i] - lastInstalled >= m) {
                count++;
                lastInstalled = point[i];
            }
        }
        return  count >= C;
    }
}