백준 1477번: 휴게소 세우기

백준 1477번: 휴게소 세우기

이분탐색문제인건 알았는데 풀이를 생각을 못해서 한참을 헤매다가 결국 다른 분들의 풀이를 확인했다. 최적의 위치를 찾는 걸로 생각하고 풀었는데 간격을 기준으로해서 풀이하면 되는 거였다.

import java.util.*;
import java.io.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N= Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+2];
        arr[0] = 0;
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        arr[N+1] = L;
        Arrays.sort(arr);

        int left = 1;
        int right = L-1;
        while(left<=right){
            int mid = (left+right)/2;
            int sum = 0;

            for(int i=1; i<arr.length; i++){
                sum+=(arr[i]-arr[i-1]-1)/mid;
            }
            if(sum>M){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        System.out.println(left);
    }


}

나는 left, right를 0,L으로 두고 좌표값으로만 생각해서 mid도 새로 추가할 휴게소의 좌표값으로 생각하니 M개일때의 경우의 수를 어떻게 계산해야할지 모르겠어서(계속 결과값이 달라질것이므로) 오래 헤맸다. 그런데 left, right를 1, L-1으로 간격값으로 두고 생각하면 이분탐색으로 해결이 된다. 역시 이분탐색은 기준값을 찾는게 제일 중요한 것 같다.