[백준] 1826 - 연료 채우기

[문제링크]

1826번: 연료 채우기

 

0. 최소 횟수로 목적지까지 도달하기 = 가능한 연료가 많은 주유소만 이용하기

 

1. 초기 이동가능 거리 X 안에 있는 주유소를 탐색

 

2. 우선순위 큐를 이용해 연료가 가장 많은 주유소를 선택, X를 X'로 갱신

 

3. X'로 거리가 늘어나며 추가로 갈 수 있게 된 주유소를 탐색

 

4. 1~3번 과정을 반복한다. X거리가 목표 거리를 초과하면 도달 성공

  - 더이상 주유소가 없는데 목표 거리에 도달하지 못하면 도달 실패

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

		PriorityQueue<Integer>pq=new PriorityQueue<>(Collections.reverseOrder());
		
		int N = pint(br.readLine());
		int[][] oil = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			oil[i][0] = pint(st.nextToken());
			oil[i][1] = pint(st.nextToken());
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int dest = pint(st.nextToken());
		int fuel = pint(st.nextToken());
		int count=0;
		int idx=0;
		
		Arrays.sort(oil, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[0]-o2[0];
			}
		});
		
		while(fuel<dest) {
			while(idx<oil.length && oil[idx][0]<=fuel) {
				pq.offer(oil[idx++][1]);
			}
			
			if(pq.isEmpty()) {
				count=-1; break;
			}
			else {
				count++;
				fuel+=pq.poll();
			}
		}
		System.out.println(count);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면