(백준) 휴게소 세우기 _ 1477

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

 

🐢 설명

처음에는 휴게소를 세울 때 기존 휴게소 사이에 (중간)에 세우면 되는게 아닌가 생각했다. 하지만 이부분은 거리가 300일 때 150으로 나눌순 있지만 100, 100, 100으로 나누는 방법은 제공하지 못한다.



새로운 접근 방법은 이분탐색이다. 휴게소간 사이 거리 S를 정하고 S일 때 휴게소를 몇개 세울 수 있나 확인한다.

이때 세운 휴게소의 수가

1. 세워야 하는 휴게소 M개보다 크다면 -> 간격이 너무 좁으므로 간격을 늘려서 휴게소를 덜 짓는다.
2. 세워야 하는 휴게소 M개보다 작거나 같다면 -> 간격을 더 줄일 수 있다는 의미이므로 간격을 줄여서 휴게소를 더 짓는다.

위와 같이 이분탐색을 통해 적절한 휴게소 사이 거리를 탐색하고, 휴게소를 지어보고, 이를 반복하면 된다.

 

참고로, 휴게소의 위치를 우선순위큐에 넣고 하나씩 빼는 방식으로 진행했는데, 이때 마지막 도착지점 (L)을 큐에 넣어줘야 한다. 그렇지 않으면 기존의 휴게소가 없을 경우에는 큐가 비어있어서 거리계산을 할 수가 없다. 

 

🐢코드

public class 휴게소세우기_1477 {
    static int N, M, L;
    static int[] restHouse;
    static PriorityQueue<Integer> housePosQ = new PriorityQueue<>();

    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());
        restHouse = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            housePosQ.add(Integer.parseInt(st.nextToken()));
        }
        housePosQ.add(L); // 종점 위치 큐에 넣어줌. 이래야 기존 휴게소가 없어도 휴게소를 지을 수 있다.

        findPos();
    }

    private static void findPos() {
        int left = 0;
        int right = 1000;
        int mid;

        while (left <= right) {
            mid = (left + right) / 2;

            int restHouseCount = houseCheck(mid);

            if (restHouseCount <= M) right = mid - 1; // 간격 더 줄임
            if (restHouseCount > M) left = mid + 1; // 간격 더 늘림
        }
        System.out.println(left);
    }

    private static int houseCheck(int span) {
        int start = 0;
        int houseCount = 0;
        PriorityQueue<Integer> tmpQ = new PriorityQueue<>();
        tmpQ.addAll(housePosQ);

        while (!tmpQ.isEmpty()) {
            int pos = tmpQ.peek();

            if ((pos - start) > span) { // 휴게소 설치
                tmpQ.add(start + span); // 현위치 + 거리에 휴게소 설치함
                start = start + span; // 현위치를 이동
                houseCount++;
            }
            else {
                tmpQ.poll(); // 휴게소가 거리 내에 있으므로 다음 휴게소 확인
                start = pos;
            }
            if (houseCount > M) break; // 휴게소 설치 개수를 이미 초과했으면 탐색 종료
        }
        return houseCount;
    }
}

 

🐢 마무리