백준 1477번 - 휴게소 세우기 (Java)

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

 

이분탐색임을 알고 들어갔는데도 뭘 이분탐색으로 잡아야할지 까다로운 문제. 체킹하는 부분도 만만치 않다.

 

이 문제의 핵심은 각 휴게소와 휴게소 사이에 거리를 이분탐색의 매개변수로 잡는 것이다.

 

1번    2번                   3번

 

세개의 휴게소가 있을 때 1번과 2번의 차이가 100이라하고 2번과 3번의 거리가 200이라하자. 만약 현재 매개변수가 70이면 1번과 2번 사이에는 1개, 2번과 3번 사이에는 2개를 지을 수 있다.

 

그러나 지을 수 있는 휴게소의 개수가 2개라면 70 에서 90정도로 늘려서 진행해볼 수 있다.

 

이 문제는 휴게소의 최소거리를 매개변수로 잡기 때문에 파라매트릭 서치로 만약 지을 수 있는 휴게소가 지금 거리로 지정했을 때 개수를 초과한다면 거리를 늘리고 초과하지 않으면 정답을 갱신한다.

 

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M, L;
        ArrayList<Integer> arrayList = new ArrayList<>();

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        L = Integer.parseInt(input[2]);

        arrayList.add(0);
        arrayList.add(L);

        if(N > 0) {
            String[] values = br.readLine().split(" ");

            for (String value : values) {
                arrayList.add(Integer.parseInt(value));
            }
        }

        Collections.sort(arrayList);

        int lo = 1;
        int hi = L - 1;
        int answer = 123131;
        while(lo <= hi){
            int mid = (hi + lo) / 2;
            int totalCnt = 0;
            for(int i = 1; i < arrayList.size(); i++){
                int len = arrayList.get(i) - arrayList.get(i - 1);

                int cnt = len / mid; // 두 휴게소 사이에 지을 수 있는 휴게소 개수
                if(cnt > 0){
                    // 딱 맞아떨어진다는 것은 마지막 휴게소와 겹쳤다는 뜻이므로 하나 빼줌
                    if(len % mid == 0) totalCnt += (cnt-1);
                    else totalCnt += cnt;
                }
            }

            if(totalCnt > M){ // 지을 수 있는 휴게소의 수 초과
                lo = mid + 1;
            }else{
                hi = mid - 1;
                answer = Integer.min(answer, mid);
            }
        }

        System.out.println(answer);
    }
}