1477 휴게소 세우기 (Java)

휴게소 세우기

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

제한

0 ≤ N ≤ 50
1 ≤ M ≤ 100
100 ≤ L ≤ 1,000
1 ≤ 휴게소의 위치 ≤ L-1
N+M < L
모든 휴게소의 위치는 중복되지 않음
입력으로 주어지는 모든 수는 정수

풀이

이 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 파라메트릭 서치로 해결 할 수 있다.
해당 문제의 답은 최소 1부터 최대 l-1 까지이다. 이 안에서 이진탐색을 통해 값을 구한 후 해당 값이 최댓값의 최솟값인지를 확인해주면 된다.
예를 들어 문제 예시에서 고속도로의 길이가 1000이기 때문에 시작값 = 1, 끝값 = 1000 - 1 = 999를 초기값으로 설정해 둔 후 이진탐색을 통해 정답을 찾는다.
mid값을 정한다면 기존 휴게소 사이에 몇개의 휴게소가 추가 되어야 하는지를 찾는다.
ex. mid = 500 :
0 ~ 200 : 0개 필요
200701 : 1개 필요
701800 : 0개 필요
800~1000 : 0개 필요
다음과 같이 값을 찾았을 때 총 필요한 휴게소의 갯수는 1개이므로 문제에서 원하는 휴게소의 갯수와는 일치한다.
그러나 우리는 최댓값의 최솟값을 찾아야한다.
지금 찾은 500의 값도 가능하지만 그보다 작은 값도 가능한지 확인한다.
즉 mid값이 세우려는 휴게소의 갯수보다 작거나 같다면 mid값을 줄이고
그렇지 않다면 mid값을 늘려 답을 찾아야 한다.

코드

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

    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());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        List<Integer> list = new ArrayList<>();
        if (n > 0) {
            list.add(arr[0]);
            list.add(l - arr[n - 1]);
        }
        if (n == 0) {
            list.add(l);
        }
        for (int i = 1; i < n; i++) {
            list.add(arr[i] - arr[i - 1]);
        }

        int start = 1;
        int end = l - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            int cnt = 0;

            for (Integer integer : list) {
                cnt += (integer-1) / mid;
            }

            if (cnt <= m) {
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }



        System.out.println(start);
    }
}