[ BOJ ][JAVA][1477] 휴게소 세우기

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

1477번: 휴게소 세우기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3857	766	588	35.125%

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 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

6 7 800
622 411 201 555 755 82

예제 출력 1

70

예제 입력 2

3 1 1000
200 701 800

예제 출력 2

251

예제 입력 3

3 1 1000
300 701 800

예제 출력 3

300

접근

일단 문제를 보자마자 이분탐색임을 알아서 조금 쉽게 풀었다.

특이한점은 처음(lo)과 마지막(hi)을 추가로 셋팅해주는 것이었고, lo = 0으로 초기화해서 시간을 오래 잡아먹었는데, 1로 초기화 해야 하더라.

0으로 하니 어떤 케이스에서 divide by zero가 나오면서 런타임에러가 걸리는 것 같다.

코드

/**
 * BOJ 1477 휴게소 세우기
 * 이분탐색
 */
import java.io.*;
import java.util.*;

public class p1477 {
    static int n, m, l;
    static List<Integer> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        list.add(0);
        list.add(l);
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);

        /**
         * lo를 0으로 잡아주니 divide by zero 런타임에러가 발생한다
         */
        int lo = 1;
        int hi = l;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (check(mid)) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        System.out.println(lo);
    }
    static boolean check(int num) {
        int cnt = 0;
        for (int i = 1; i < list.size(); i++) {
            cnt += (list.get(i) - list.get(i - 1) - 1) / num;
        }
        if (cnt > m) return true;
        return false;
    }
}