백준 - 2110 ( Java ) - 매개변수 탐색

이분 탐색이 binary search인것은 이미 알 수 있다. 그렇다면 매개 변수 탐색은 무엇일까?

 

매개 변수 탐색(Parametric Search )이란?

 

이분 탐색과 매우 유사하지만 매개 변수 탐색은 결정 문제라는 것.

 

결정문제라는 뜻은 구한 임의의 값이 정답인지 아닌지 판별해가며 정답을 찾아가는 문제라는 뜻입니다.

 

이 "임의의 값"을 매개 변수 탐색 방법에선 이분 탐색에서 해를 찾는것과 유사하게 찾아냅니다.

 

 

예시 문제 - 백준 2110

 

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

2110번: 공유기 설치

 

코드

 

import java.util.Scanner;
import java.util.Arrays;
 
public class Main {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int c = sc.nextInt();
        int [] xi = new int[n];
 
        for (int i = 0; i < n ; i++)
            xi[i] = sc.nextInt();
 
        Arrays.sort(xi);
 
        int left = 1;
        int right = xi[n-1] - xi[0];
        int d = 0;
        int ans = 0;
 
        while (left <= right) {
 
            int mid = (left + right) / 2;
            int start = xi[0];
            int cnt = 1;
 
            for (int i = 1; i < n ; i++) {
                d = xi[i] - start;
                if (mid <= d) {
                    ++cnt;
                    start = xi[i];
                }
            }
 
            if (cnt >= c) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
 
        System.out.println(ans);
    }
}

 

 

 

집의 개수가 N 개이고 집의 좌표는 xi , 공유기의 개수가 C 라고 할 때 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 문제입니다.

 

 

여기서 임의의 최대거리를 이분 탐색과 유사하게 만듭니다.

 

while (left <= right) {
 
    int mid = (left + right) / 2;
    int start = xi[0];
    int cnt = 1;
 
          

 

그 후에 최대거리가 참인지 거짓인지 판별하는 일을 합니다.

 

for (int i = 1; i < n ; i++) {
    d = xi[i] - start;
    if (mid <= d) {
        ++cnt;
        start = xi[i];
    }
}
 
if (cnt >= c) {
    ans = mid;
    left = mid + 1;
}
else {
    right = mid - 1;
}