[백준 1826] 연료 채우기 - JAVA

문제 정의

• 1km에 1L씩 연료를 사용하는 트럭이 0에 위치
• 주유소의 위치 a와 충전할 수 있는 연료량 b 가 주어짐
• 최종 목적지인 마을의 위치 L과 현재 트럭의 보유 연료량 P가 주어질 때
• 트럭이 마을까지 도착하기 위해 주유소에 방문하는 최소 횟수를 구해라

접근 방법

두 개의 우선순위 큐

최소 횟수가 되기 위해서는
현재 연료로 주유를 할 수 있는 위치에 있는 주유소들을 모두 찾고
그 주유소 중 최대로 연료를 충전하는 주유소를 방문하는 것입니다.

그러기 위해서는
거리 순으로 정렬되는 watingQueue를 선언해서
현재 방문할 수 있는 주유소인지 확인하고

waitingQueue에 있는 주유소들을 candidateQueue로 옮겨
현재 시점에서 어떤 주유소를 방문하는 것이 가장 최적인지 탐색합니다.

그 중 하나를 꺼내 그만큼 이동 거리를 증가시키고
다음 while에서 반복합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<int[]> waitingQueue = new PriorityQueue<>((o1, o2) -> {
            return o1[0] - o2[0];
        });

        PriorityQueue<int[]> candidateQueue = new PriorityQueue<>((o1, o2) -> {
            return o2[1] - o1[1];
        });

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            waitingQueue.offer(new int[]{a, b});
        }

        st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        int count = 0;
        while (true) {
            if (P >= L) break;

            while (!waitingQueue.isEmpty() && waitingQueue.peek()[0] <= P) {
                candidateQueue.offer(waitingQueue.poll());
            }

            if (candidateQueue.isEmpty()) {
                count = -1;
                break;
            }

            P += candidateQueue.poll()[1];
            count++;
        }

        System.out.println(count);
    }
}