백준 1826 : 연료 채우기

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

1826번: 연료 채우기

[ 문제풀이 ]

주유소를 사용하는 비용이 모두 동일하기 때문에 더 이상 이동할 수 없는 경우 현재 이동한 거리 내의 주유소 중 최대 연료의 양을 가지는 주유소를 선택하는 것이 최선의 선택이다.

따라서 주유소를 연료의 양을 기준으로 우선순위 큐에 저장해놓으면서 더 이상 이동할 수 없을 경우 이동할 수 있는 연료의 양을 만들어주면 된다.

연료를 만드는 도중 우선순위 큐가 비어서 이동할 수 없거나 모든 주유소를 사용했음에도 불구하고 도착지점을 갈 수 없다면 -1을 출력해주면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class Station implements Comparable<Station> {
		int pos, fuel;

		Station (int pos, int fuel) {
			this.pos = pos;
			this.fuel = fuel;
		}

		@Override
		public int compareTo(Station o) {
			return this.pos - o.pos;
		}
	}
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			int N = Integer.parseInt(br.readLine());
			Station[] stations = new Station[N];
			for (int i = 0; i < N; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int pos = Integer.parseInt(st.nextToken());
				int fuel = Integer.parseInt(st.nextToken());
				stations[i] = new Station(pos, fuel);
			}
			
			Arrays.sort(stations);
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int L = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());

			PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
			int count = 0;
			for (int i = 0; i < N; ++i) {
				if (P >= L) break;
				if (stations[i].pos > P) {
					while (!pq.isEmpty() && stations[i].pos > P) {
						count++;
						P += pq.poll();
					}
					if (stations[i].pos > P) break;
				}
				pq.offer(stations[i].fuel);
			}
			
			while (!pq.isEmpty() && P < L) {
				count++;
				P += pq.poll();
			}
			bw.write((P >= L ? count : -1) + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}