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

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

1826번: 연료 채우기

[문제]

[풀이]

현재 연료상태를 curFuel 이라고 하면 , 이 연료로 어느 주유소까지 갈 수 있는지 검사해야한다.
연료가 많은 순으로 정렬된 우선순위큐를 fuelQ라고 하자.

주유소 거리순으로 정렬한 뒤에 하나씩 뽑아보면서
1. 만약 갈수 있다면 연료큐(fuelQ)에 push
2. 갈수 없다면 
 2-1. 연료큐가 비어있으면 끝. (연료가 모자라서 갈수 없음)
 2-2. 연료큐에 있는 연료를 하나 빼먹고 카운트 증가. && curFuel(현재연료) 에 빼먹은 연료를 더함 (curFuel+=fuelQ.poll() )

이걸 curFuel 이 마을에 도착할 때 까지 반복해주면 된다.

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
 
public class Main {
 
    static Queue<int[]> q;
    static Queue<Integer> fuelQ;
    static int town,curFuel;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        q = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]); // 거리순 heap
        fuelQ = new PriorityQueue<>(Collections.reverseOrder());
 
        for(int i=0;i<n;i++)
            q.add(Arrays.stream(br.readLine().split(" "))
                            .mapToInt(Integer::parseInt).toArray());
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        town = input[0];
        curFuel = input[1];
 
        System.out.println(getCount());
 
    }
    static int getCount(){
        int ans=0;
        while (curFuel<town){
            while (!q.isEmpty() && q.peek()[0]<=curFuel)
                fuelQ.add(q.poll()[1]);
 
            if(fuelQ.isEmpty()) return -1;
 
            ans++;
            curFuel+=fuelQ.poll();
        }
 
        return ans;
    }
}