[백준 1477] 휴게소 (JAVA)

문제

---

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

풀이

---

고속도로 끝에는 휴게소를 지을 수 없지만 거리는 계산이 되므로 포함시켜야 합니다. 휴게소 간의 거리를 배열에 저장 후(양쪽 끝도 포함) 이분 탐색으로 기준 거리를 정한 후 휴게소 사이에 몇개의 휴게소를 놓을 수 있는지 확인합니다. 만약에 더 많이 놓을 수 있으면 거리를 늘리고 부족하면 거리를 줄이면 됩니다.

휴게소 간격	82	119	210	144	67	133	45	추가한 휴게소
60	1	1	3	2	1	2	0	10
70	1	1	2	2	0	1	0	7
80	1	1	2	1	0	1	0	6

코드

---

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

public class Main {

    static int N, M, L;
    static int[] rest, restLen;

    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());
        rest = new int[N+1];
        restLen = new int[N+1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            rest[i] = Integer.parseInt(st.nextToken());
        }
        rest[N] = L;
        Arrays.sort(rest);

        int temp = 0, max = Integer.MIN_VALUE;
        for (int i = 0; i <= N; i++) {
            restLen[i] = rest[i] - temp;
            max = Math.max(restLen[i], max);
            temp = rest[i];
        }

        System.out.println(binarySearch(max));
        br.close();
    }

    public static int binarySearch(int max) {
        int ans = 0;
        int left = 1, right = max;
        while (left <= right) {
            int mid = (left + right) >> 1;

            if (check(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }

    public static boolean check(int mid) {
        int cnt = 0;
        for (int i : restLen) {
            if (mid >= i) continue;
            cnt += Math.ceil(i / (double)mid) - 1;
        }

        if (cnt <= M) return true;
        return false;
    }
}