백준 2110 : 공유기 설치

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

최적화 문제를 결정 문제("예" 또는 "아니오"로 대답할 수 있는 문제)로 바꾸어 푸는 파라메트릭 서치 문제이다. 여기서 최적화 문제는 "가장 가까운 공유기 거리를 최대화"하는 것이고, 결정 문제는 "주어진 거리로 공유기 C개를 설치할 수 있는가"이다.
check() 함수는 mid거리가 주어졌을 때, C개의 공유기를 설치할 수 있는지 여부를 판단한다.

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N, C;
    static int[] arr = new int[200001];
    static int ans = 0;

    private static boolean check(int mid) {
        int s = arr[0];
        int cnt = 1;
        for(int i = 1; i < N; i++){
            if(arr[i] - s >= mid){
                cnt++;
                s = arr[i];
            }
        }


        if(cnt >= C) return true;
        return false;
    }

    public static void main(String[] args) {
        N = sc.nextInt();
        C = sc.nextInt();

        for(int i = 0; i < N; i++){
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr, 0, N);

        int left = 0;
        int right = arr[N - 1] - arr[0];

        while(left <= right){
            int mid = (left + right) / 2;

            // 거리 mid에 대해 집의 개수를 만족한다면
            if(check(mid)){
                ans = Math.max(ans, mid);
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        System.out.println(ans);
    }
}