[BOJ] 1477. 휴게소 세우기 (🥇, 이분 탐색)

🔗

풀이

휴게소가 없는 구간의 길이 값을 탐색하는 것이 목적이다. 해당 구간은 1보다 크고, 고속도로의 최대 길이보다는 반드시 작다. 문제에서 주어지는 L은 1000이 최대값이기 때문에 결국 휴게소가 없는 구간의 값은 1 ~ 1000 내에 존재한다고 할 수 있다.

1~1000 내의 임의의 값을 현재 휴게소가 없는 구간의 최대값으로 임의로 정한다.

6 7 800
622 411 201 555 755 82

위의 예제를 기준으로 400을 휴게소가 없는 구간의 최대값으로 정한다고 가정하자. 휴게소들의 위치는 오름차순 정렬하면 아래와 같다

(1) 82 201 411 555 622 755 (800)

휴게소가 없는 구간의 최대가 400이기 때문에 각 휴게소들의 간격을 계산해서 400을 넘어가는 값들에 대해서는 400보다 작아질 수 있도록 사이에 휴게소를 설치하면 된다. 400을 기준으로 했을 때는 모든 휴게소 간의 간격이 400보다 작기 때문에 휴게소를 하나도 설치 하지 않아도 된다. 이렇게 기준 간격이 굉장히 넓어서 설치해야 하는 휴게소의 개수가 M개 보다 작은 경우에 대해서는 최대 M을 채우기 위해서 아무데나 휴게소를 설치하면 된다. 1 ~ 82 사이에 7개의 휴게소를 다 설치해도 휴게소가 없는 구간의 최대값에는 영향을 주지 않기 때문이다.

만약 기준을 50으로 하게 되면 1~82 사이에 1개, 82~201 사이에 2개, 411 ~ 201 사이에 4개, 411 ~ 555 사이에 2개로 설치해야 하는 휴게소의 개수가 7개를 넘어가게 된다. 이때는 기준을 더 높여야 한다.

가능한 모든 경우의 수에 대해서 완전 탐색을 하게 되면 탐색의 횟수가 백만을 넘어가기 때문에 O(logN)의 시간을 보장하는 이분 탐색으로 탐색을 진행한다.

import java.util.*;
import java.io.*;

public class Main {
    static int[] restStop;
    
    static int run(int mid) {
        int count = 0;
        for (int i = 1; i <= restStop.length-1; i++) {
            int distance = restStop[i] - restStop[i-1] - 1;
            count += (distance / mid);
        }
        return count;
    }

    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 M = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        
        restStop = new int[N+2];
        restStop[0] = 1;
        restStop[N+1] = L;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            restStop[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(restStop);

        int low = 1; 
        int high = L;
        while (low <= high) {
            int mid = (low + high) / 2;

            if (run(mid) <= M) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        System.out.println(low);
    }
}