[백준 - 1826] 연로 채우기 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 우선순위 큐

입력

첫째 줄에 주유소의 개수 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)은 성경이의 위치에서 마을까지의 거리, P(1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

모든 주유소와 마을은 서로 다른 좌표에 있고, 마을은 모든 주유소보다 오른쪽에 있다.

출력

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

풀이

우리는 주유소를 최소한으로 멈춰서 마을까지 가야된다.

그러면, 현재 연료를 최대한 사용하고, 지나온 주유소 중에 더 멀리갈 수 있는 주유소를 고르는게 최선의 선택이라 할 수 있다.

예를 들어
주요소가 다음과 같이 4개 있고,
1. (4, 4)
2. (5, 2)
3. (11, 5)
4. (15, 10)

처음 연료인 P = 10;
마을까지 거리가 25인 경우

P가 10이기 때문에 10까지는 어떤 주유소에 멈추지 않아도 갈 수 있다.
그렇지만, 마을이 10보다 멀리 위치해 있기 때문에 지나온 주유소가 필요하며, 이 주유소 중 당연히 연료를 가장 많이 충전할 수 있는 주유소가 최선의 선택이 된다.

그래서 P가 10일 때 첫 번째 주유소에 멈췄다는 의미로 4를 충전해준다.
그러면 14까지는 하나의 주유소만으로 갈 수 있다. 아직 마을까지 도착 못했기 때문에 똑같이 지나온 주유소 중 최선의 선택을 한다.

그러면 3 번째 주유소이기 때문에 P는 다시 5가된다.
그래서 19까지 두개의 주유소만으로 갈 수 있고, 아직 마을의 도착 못했기 때문에 4번 째 주유소에서 충전하면 총 3개의 주유소로 원하는 마을에 도착한다.

그래서 주유소에 최소한으로 멈춘 횟수는 3이 된다.

지나온 주유소는 충전하는 연료를 기준으로 내림차순하는 우선순위 큐에 넣고, P가 0일 때마다 pq.poll()하면 된다.

그래서 시간 복잡도는 O(N * logN)이 된다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        int[] gas = new int[1000001];
        
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            gas[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }
        
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        
        int L = Integer.parseInt(st2.nextToken());
        int P = Integer.parseInt(st2.nextToken());
        
        int coutGas = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for(int i=1; i<=L; i++) {
            if(gas[i] != 0) {
                //주유소가 있음
                pq.add(gas[i]);
            }
            P -= 1;
            if(i == L) {
                break;
            }
            if(P == 0) {
                
                if(pq.size() == 0) {
                    coutGas = -1;
                    break;
                }
                coutGas += 1;
                P += pq.poll();
            }
        }
        System.out.println(coutGas);
        
    }
}