[백준 01477] 휴게소 세우기 [Java]

문제

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

 

---

풀이

구간 1 ~ (L - 1)에 N개의 휴게소가 위치 A[i]에 존재하고, M개의 휴게소를 추가로 지었을 때, 휴게소가 없는 구간의 길이의 최댓값이 최소가 되도록 해야 한다.

문제의 설명에서 알 수 있듯.

1. M개의 휴게소를 전부 설치 가능한 경우에 대해
2. 휴게소가 없는 구간의 길이의 최댓값이 최소가 되어야 한다.

휴게소가 없는 구간의 길이를 탐색 범위로 잡고, 이분 탐색을 하면 된다.

배열 A의 앞 뒤에 경계 값을 붙여주어 계산을 쉽게 해보자.

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Init
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // Input
        st = new StringTokenizer(br.readLine());
        final int N = Integer.parseInt(st.nextToken());
        final int M = Integer.parseInt(st.nextToken());
        final int L = Integer.parseInt(st.nextToken());
        int[] A = new int[N + 2];
        A[0] = 0;
        A[N + 1] = L;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        } 

전체 구간(left, right)에 대해 이분 탐색으로 길이를 조절하며

모든 휴게소의 중간 거리를 나눈 몫을 세주면 된다.

        // Solve
        Arrays.sort(A);
        int left = 1, right = L - 1;
        while (left <= right) {
            final int mid = (left + right) >> 1;
            int cnt = 0;
            for (int i = 1; i < N + 2; ++i) {
                cnt += (A[i] - A[i - 1] - 1) / mid;
            }

이때 휴게소는 M개를 지어야 하므로 만약 몫과 건설 가능한 휴게소의 수 M과 비교하며 범위를 좁히면 된다.

            if (cnt > M) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // Output
        System.out.print(left);
    }
}

---

소스코드

보기