백준 1826 연료 채우기(우선순위 큐, 그리디)★★

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

1826번: 연료 채우기

주유소에 최대한 적게 가야한다는 것을 보고 그리디적으로 접근해야됨을 알았다.

어떻게 하면 최대한 적게 갈 수 있을까?

 

내가 보유한 P만큼 앞으로 나갈 수 있는데 P만큼 전진 했을 때 만약 도착지점에 가지 못했다면

지나친 주유소들 중 연료를 가장 많이 주는 곳에서 채우는게 가장 이득이지 않겠는가?! ==> Max-Heap

 

거리는 1,000,000이기 때문에 크기가 1,000,000인 int[] 만들어서

index = 주유소 거리, value = 채울 수 있는 연료량을 한다.

 

for 0 ~ L까지 나아가면서 1km당 1L니까 for문이 돌 때 마다 P--;가 될 것이며지금까지 오면서 만났던 주유소의 기름들을 Max-Heap으로 넣어준다

why?)

만약 기름이 부족하면 지금까지 만났던 주유소들 중 기름 많이 주는곳에서 채우는게 이득이니까

 

기름이 0이 될때마다 poll()을 해주면서 기름을 채워주고 cnt++해준다.

package practice;

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

public class Main_1826 {

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

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

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

		int[] gas_station = new int[1000001];

		for (int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");
			gas_station[Integer.parseInt(input[0])] = Integer.parseInt(input[1]);
		}
		String[] input = br.readLine().split(" ");
		int L = Integer.parseInt(input[0]);
		int P = Integer.parseInt(input[1]);

		for (int i = 0, j = 0; i < L; i++, P--) {
			if (gas_station[i] != 0)
				fuel.add(gas_station[i]);

			try {
				if (P == 0) {
					P += fuel.poll();
					res++;
				}
			} catch (Exception e) {
				System.out.println(-1);
				return;
			}
		}

		System.out.println(res);

	}

}