[백준] 1477: 휴게소 세우기 - JAVA

in Algorithm on 기타

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

풀이

이분탐색으로 풀어야겠다는 생각이 바로 들지 않았다.

우선순위큐를 이용해 풀어보려고했는데 잘 되지 않아서 구글링의 도움을 받았다.

이분탐색을 하는데 휴게소들 사이의 거리를 기준으로 탐색한다. 이분탐색을 어떤걸 기준으로 하는지 찾는 것이 어려웠다.

휴게소 간 거리이기때문에 left를 1로, right를 l-1로 놓고 진행했다.

mid만큼의 거리를 두고 이미 있는 휴게소들 사이에 mid만큼 거리로 몇 개나 더 세울 수 있는지 체크한다.

이렇게 헤아린 개수를 통해 구간을 좁혀나간다.

메모리: 14268KB

시간: 128ms

언어: Java 11

코드

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

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

        int left = 1;
        int right = l - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int sum = 0;
            for (int i = 1; i < n + 2; i++) {
                sum += (arr[i] - arr[i - 1] - 1) / mid;
            }

            if (sum > m) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(left);
    }

}