[Java] 백준 1477번 : 휴게소 세우기

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

1477번: 휴게소 세우기

---

💡 문제 풀이

이분 탐색 문제이다.

 

세워야 할 휴게소만큼 각 구간 별로 확인해서 모두 세울 수 있는지 확인하면 된다.

검색할 값은 휴게소간의 거리이고, 확인 값은 주어진 거리로 휴게소를 세울 때 조건만큼 세울 수 있는지이다.

시작 범위(0부터)와 마지막 범위(고속도로 끝까지)도 따져야 하므로 0과 l을 리스트에 추가해 준다.

✔️ 느낀 점

이분 탐색에 부족함을 느끼고 풀었던 문제인데, 생각보다 금방 풀었다.

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = getBufferedReader();
    static int n, m, l;
    static List<Integer> locations;

    public static void main(String[] args) throws IOException {
        initInputs();
        initLocations(n);

        int minDistance = getMinDistance();
        System.out.println(minDistance);
    }

    private static int getBuildableCount(int minDistance) {
        int count = 0;

        for (int i = 1 ; i < locations.size() ; i++) { 
            int distance = locations.get(i) - locations.get(i - 1) - 1;
            count += distance / minDistance;
        }

        return count;
    }

    private static int getMinDistance() {
        int start = 1;
        int end = l - 1;

        while (start <= end) {
            int middle = (start + end) / 2;
            int buildable = getBuildableCount(middle);

            if (buildable > m) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }

        return start;
    }

    private static void initInputs() throws IOException {
        StringTokenizer st = getTokenizer();
        n = getIntFromToken(st);
        m = getIntFromToken(st);
        l = getIntFromToken(st);
    }

    private static void initLocations(int n) throws IOException {
        locations = new ArrayList<>(List.of(0, l));
        StringTokenizer st = getTokenizer();

        for (int i = 0 ; i < n ; i++) {
            locations.add(getIntFromToken(st));
        }

        Collections.sort(locations);
    }

    private static int getIntFromToken(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }

    private static StringTokenizer getTokenizer() throws IOException {
        return new StringTokenizer(br.readLine());
    }

    private static BufferedReader getBufferedReader() {
        return new BufferedReader(new InputStreamReader(System.in));
    }
}