자바 - 백준 1477 / 휴게소 세우기

백준 1477 휴게소 세우기
골드4

구현 방법

처음에 그리디 방식으로 생각했다.
가장 긴 구간대를 꺼내 반으로 나누는 것을 반복하면 될거라고 생각했으나, 이 경우 최댓값의 최소값 조건을 만족하 못하는 경우가 발생했다.
예를 들어, 구간이 300 140이고 두번 나눌 수 있다고 했을 때 150, 150, 140 -> 75, 75, 150, 140으로 150이 된다.
하지만 실제로 300을 두번 나누어 100, 100, 100, 140이 되기 때문에 140이 될 수 있다.

세울 수 있는 휴게소의 범위 1 - 100, 도로 길이의 범위 100 - 1000으로 범위가 작다. 또한 만족하는 최댓값의 최소값을 구해라고 했다.
정리하면 범위 내에서 가능한 모든 경우를 고려하여 최솟값을 구해야한다. 하지만 모든 범위를 하나하나 탐색할 경우 시간이 오래걸린다.
이를 통해 매개변수 탐색 알고리즘을 적용하면 된다고 생각했다.


주의 사항

1. 출발지와 도착지점에는 휴게소가 없기 때문에 구간에 포함시켜 주어야 한다.
2. 휴게소가 없는 구간에서 목표하는 구간 길이를 나누어 몇개의 휴게소가 추가로 필요한지 구하는 과정에서 (휴게소가 없는 구간 - 1)을 해 주어야 한다.
   이유는 만약 휴게소가 없는 구간이 9이고 목표하는 구간은 3이라고 했을 때 (9 -1) / 3을 해야 2로 나오기 때문이다.(두번 나누면 구간이 3으로 나누어진다는 뜻)

코드

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

/**
 * 백준 1477
 * 휴게소 세우기
 * 골드4
 * https://www.acmicpc.net/problem/1477
 */
public class Boj1477 {

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

        Arrays.sort(rest);

        int start = 1;
        int end = L;
        int result = 0;

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

            if (isPossible(mid, M, rest)) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        System.out.println(result);
    }

    public static boolean isPossible(int target, int M, int[] rest) {
        int cnt = 0;

        for(int i = 1; i < rest.length; i++) {
            int dif = rest[i] - rest[i - 1];
            cnt += (dif - 1) / target;
        }

        return cnt <= M;
    }
}