BOJ 2110 공유기 설치

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

파라메트릭서치 사용해서 이분탐색했다.
👇👇이분탐색, 파라메트릭서치가 궁금하다면?
Binary Search(이분탐색)

1. 최소값(0) 최대값(home[N-1] - home[0]) 찾는다
2. 최소,최대값 가지고 이분탐색을 한다
3. 중간값이 C보다 작다 => mid값이 더 작아야한다 => 앞부분 탐색
4. 중간값이 C보다 크다 => mid값이 더 커야한다 => 뒷부분 탐색

밑에 코드에서 C보다 작지 않으면 answer 업데이트해주는데 왜 이렇게 한건가요?

우리가 구하려는 것은 공유기사이의 최소거리입니다! 즉, 최대거리는 상관없다는 말이죠! mid거리에 맞춰서 공유기를 놓다보니 C개수보다 많이 놓을 수 있습니다. 그러면 초과된만큼 공유기를 제거해도 됩니다(제거하면 거리가 늘어나기 때문에 최소거리에 영향x)

=> 즉, 답이 될수 있다는 소리!

mid와 realMid는 어떤 차이인가요?

mid는 답이라고 예상한 값입니다. 즉, 공유기간의 최소거리란 의미! 그래서 possibleDist값이 다음에 올 수 있는 가장 가까운 거리입니다.

만약 possibleDist에 집이 없다면??? 그 뒤에 있는 실제 집에 공유기를 설치해야합니다. 그런데 이렇게 되면 실제 최소거리가 mid가 아니게 됩니다 => 그래서 realMid를 하나 생성해서 실제 최소거리를 설정해주었습니다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CMain_2110 {
    private static int answer=0;
    private static int[] home;
    private static int N,C;
    private static int max;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        home = new int[N];

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

        Arrays.sort(home);
        max = home[N-1] - home[0];

        binarySearch(0,max);
        System.out.println(answer);
    }

    private static void binarySearch(int start, int end) {
        if(start==end) return;

        int mid = (start+end)/2; //탐색할 가장 인접한 거리
        int realMid=Integer.MAX_VALUE;
        int cnt = 1;
        int idx = 0; //현재 공유기위치
        int possibleDist = home[idx]+mid; //다음에 공유기 설치 가능한 집 위치

        while(idx<N-1) {
            idx++;
            if(home[idx]>=possibleDist) {
                System.out.println(home[idx]+" "+possibleDist);
                realMid = Math.min(realMid, mid+home[idx]-possibleDist);
                cnt++;
                possibleDist = home[idx]+mid;
            }
        }

        //System.out.println(start+" > "+end+"("+mid+" "+realMid+")"+" : "+cnt);

        if(cnt<C) binarySearch(start,mid);
        else{
            answer = Math.max(answer,realMid);
            binarySearch(mid+1, end);
        }

    }

}