문제

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

---

입력

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

---

출력

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

---

풀이

제한조건

• 1 ≤ N ≤ 10,000
• 1 ≤ a ≤ 1,000,000
• 1 ≤ b ≤ 100
• 1 ≤ L ≤ 1,000,000
• 1 ≤ P ≤ 1,000,000
• 모든 주유소와 마을은 서로 다른 좌표에 있고, 마을은 모든 주유소보다 오른쪽에 있다.

접근방법

그리디

N, L, P의 범위를 고려했을 때, 완전 탐색으로는 풀 수 없다.
구하고자 하는 값은 최소값으로 그리디 또는 DP 유형의 문제라고 추측할 수 있다.

예시를 바탕으로 그림으로 표현해서 다시 생각해보자.

현재위치에서 갈 수 있는 주유소 중 가장 많이 연료를 충전할 수 있는 주유소를 목표로하여 이동
이 반복되며 문제를 풀 수 있음이 보인다.

즉 그리디하게 선택하여 문제를 해결 할 수 있기에 그리디로 접근한다.
( 이 문제는 중복되는 부분 문제가 없다 또한 문제의 메모리 제한이 작기에 메모리 공간을 많이 활용하는 DP가 아닐 것이다!

위의 조건을 만족하게 구현하기 위해서는 거리순으로 정렬된 데이터와 연료 순으로 정렬된 데이터가 필요하다.

• Array 또는 List를 사용하여 정렬하는 방식
• Heap을 이용하여 찾는 방식

위의 두 가지 방법 중 하나를 선택하여 진행해야한다.
여기서는 우선순위 큐를 활용하여 진행했다.
( Array 또는 List를 사용할 경우, 인덱스 관리가 귀찮다. -> 코드 복잡)

문제를 풀이하는 과정에서 주유소의 위치가 현재위치보다 전에 있는지, 이후에 있는지에 따라 다르게 처리해준다면 어렵지 않게 해결 할 수 있다.

코드를 참조해보자.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	static int N, L, P;

	static class Pair {
		int first;
		int second;

		Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader((System.in)));
		N = stoi(in.readLine());

		// 거리순 정렬
		PriorityQueue<Pair> sortByDist = new PriorityQueue<>((a, b) -> a.first - b.first);
		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
			sortByDist.add(new Pair(stoi(inputs[0]), stoi(inputs[1])));
		}
		String[] inputs = in.readLine().split(" ");
		L = stoi(inputs[0]);
		P = stoi(inputs[1]);

		// 충전량이 많은 순
		PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> b.second - a.second);

		int curPosition = 0;
		int stopCount = 0;

		while (true) {
			// 현재 이동 가능한 주유소를 모두 pq에 추가한다.
			while (!sortByDist.isEmpty() && sortByDist.peek().first <= curPosition + P)
				pq.add(sortByDist.poll());

			// 이동 가능한 주유소가 없다.
			if (pq.isEmpty())
				break;

			// 도착지에 도달 가능하다.
			if (curPosition + P >= L)
				break;

			Pair cur = pq.poll();
			stopCount++;
			if (curPosition < cur.first) {
				// 가는 길에 있는경우
				P -= (cur.first - curPosition); // 이동비용
				P += cur.second; // 보충
				curPosition = cur.first; // 위치갱신
			} else {
				// 이전에 들렸어야 했던 경우
				P += cur.second;
			}
		}

		if (curPosition + P >= L)
			System.out.println(stopCount);
		else
			System.out.println(-1);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}