백준 1826번 - 연료 채우기

문제

백준 1826번 - 연료 채우기

아이디어

• 횟수를 최소화 하기 위해서는 이동 가능한 범위 내에 있는 주유소들 중에 가장 많은 연료를 채우면서 P에서 L까지 가는 것이 유리할 것이다.
• 주유소 정보를 거리 기준으로 오름차순 정렬하여 이동 가능한 범위를 정확히 탐색하도록 한다.
• 내림차순 우선순위큐를 사용해 범위 내에 있는 주유소 중 채울 수 있는 연료의 양이 가장 많은 주유소에서 멈출 수 있도록 한다.
• P < L 까지 반복하면서 이동한 횟수가 정답이 된다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N log N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_1826 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        st = new StringTokenizer(br.readLine());

        int L = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> qu = new PriorityQueue<>(Collections.reverseOrder());

        int idx = 0;
        int count = 0;

        while (P < L) {

            while (idx < n && arr[idx][0] <= P) {
                qu.offer(arr[idx][1]);
                idx++;
            }

            //도착하기 전에 이동할 수 있는 주유소가 없다면 불가능
            if (qu.isEmpty()) {
                System.out.println(-1);
                return;
            }

            P += qu.poll();
            count++;
        }

        System.out.println(count);

    }
}