백준 1826번 - 연료 채우기 Java

문제

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

---

입력

 

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

---

출력

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

---

해결 방법

주유소에서 멈추는 횟수가 최대한 적어야 한다.

 

따라서 우선 연료가 다 떨어질 때 까지 최대한 이동해본다. 이 때 길을 지나치면서 만나는 주유소는 전부 후보로 저장해둔다. 만약 연료를 다 쓰고도 도착지에 도착하지 못하면, 이 때 까지 지나온 주유소의 연료량 중 가장 높은 것을 충전해서 다시 길을 이동한다. 이 때 멈추는 횟수는 1 증가하게 된다.

 

예제를 보도록 하자

 

처음 연료 : 10

마을 까지의 거리 : 25

 

우선 처음 주어진 연료로 최대한 이동해보자. 이 때 지나가면서 마주치는 주유소는 1번과 2번으로, 각각 4와 2의 연료를 충전해준다.

 

 

이제 이동을 계속해야 하는데, 남은 연료량이 없다. 따라서 후보 연료중 가장 높은 4를 충전해서 계속 이동한다. 

 

그러면 14에서 연료가 다 떨어지고, 이 때 지나온 주유소 중 3번 주유소에서 5의 연료를 충전한다. 그리고 19 까지 가도 연료가 떨어지는데, 4번 주유소에서 연료 10을 충전한다. 이후 남은 연료를 가지고 정상적으로 마을에 도착할 수 있고, 충전한 연료는 3개기 때문에 답은 3이 된다.

 

길을 지나가며 만나는 주유소는 모두 PriorityQueue 로 관리해준다. 연료를 충전할 때 가장 높은 연료를 충전하면서 가는게 정답이기 때문이다.

 

public class P1826 {

    static int[] fuel = new int[1000001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer input = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(input.nextToken()); //시작 위치에서 주유소 까지의 거리
            int b = Integer.parseInt(input.nextToken()); //주유소에서 채울 수 있는 연료의 양
            fuel[a] = b;
        }
        StringTokenizer lastInput = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(lastInput.nextToken()); //성경이의 위치에서 마을까지의 거리
        int P = Integer.parseInt(lastInput.nextToken()); //원래 있던 연료의 양

        //1KM 이동 시 1L 사라짐

        System.out.println(solution(L, P));
    }

    static int solution(int L, int P) {
        int ret = 0;
        PriorityQueue<Integer> fuels = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 0; i < L; i++, P--) {
            //현재 위치에 주유소가 있으면 후보 주유소에 넣는다
            if (fuel[i] != 0) {
                fuels.add(fuel[i]);
            }
            //이동하기 전 연료가 0이면, 현재까지 지나온 주유소에서 연료를 채움 (제일 큰 거)
            if (P == 0) {
                //연료가 없는데 찾은 주유소도 없으면, 도착 못 함
                if (!fuels.isEmpty()) {
                    P += fuels.poll();
                    ret++;
                } else {
                    return -1;
                }
            }

        }
        return ret;
    }
}