Parametric search (파라메트릭 서치)

이진탐색의 응용버전

 

최적화문제 = 이진탐색 + 결정문제(YES/NO)

 

 

설명 : 범위의 중간값을 해(x)로 설정하고 조건을 판별하면서 찾아야할 범위를 반씩 줄여나간다.

 

시간복잡도 : log N

 

---

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

2110번: 공유기 설치

1. 초기값으로 최소, 최대거리 설정

 

2. 중간값 (mid) 를 해 (x)로 하여 조건과 부합하는지 판별

 

3. 

1. 공유기 설치 개수가 목표 C 같거나 크다면 이제 문제에서는 공유기 사이의 거리의 최대값을 요구하기 때문에 목표 거리를 늘려준다.  =>  left = mid+1
2. 공유기 설치 개수가 목표 C보다 작다면 공유기 사이 거리값을 줄여주면 더 많은 공유기를 설치할 수 있기 때문에 거리를 줄여준다. => right = mid-1

 

public class Main {

    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());

        int[] loc = new int[N];

        for (int i = 0; i < N; i++)
            loc[i] = Integer.parseInt(br.readLine());

        Arrays.sort(loc);

        int left = 1, right = loc[N - 1] - loc[0];
        int ans = 0;

        while (left <= right) {
            int mid = (left + right) / 2; // x
            int cnt = 1;
            int cur = loc[0];
            for (int i = 1; i < N; i++) {
                if (loc[i] - cur >= mid) {
                    cnt++;
                    cur = loc[i];
                }
            }
            if (C <= cnt) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(ans);

        br.close();
    }
}