[백준 1826] 연료 채우기

연료채우기 1826

유형

• 그리디

풀이

주유소에 들리는 횟수를 최소화해야 하기 때문에 현재 연료로 갈 수 있는 주유소 중에서 최대한 멀리 또는 주유소를 갔을 때 연료가 가장 많아지는 경우 둘 중에 하나로 가야 최소가 되는 경우를 찾을 수 있을 것이라고 생각이 들었다.

우선 현재 연료로 가장 멀리 간다고 하였을때에는
N = 2 L = 14 P = 4
(2,3) (4,7)
이런 예제에서는 -1을 출력하게 된다. 현재 연료 4에서 가장 멀리 갈 수 있는 경우는 4번 주유소를 가는 것이고 그렇게 되면 도착점 14를 갈 연료가 부족하게 된다. 그렇기 때문에 현재 연료에서 가장 먼 주유소를 가는 방법은 틀렸다.

두번째 현재 연료로 갈 수 있는 주유소 중에서 충전했을 때 연료가 가장 많아지는 경우를 생각해보자.
더 자세히 말하면 현재 갈 수 있는 주유소 중 가장 연료를 많이 얻을 수 있는 순으로 택하는 것이다. 위 예제에서 현재 연료로 가장 많이 얻을 수 있는 곳은 4번 주유소이다. 4번으로 갔을 때 연료는 7이 되고 여전히 도착점 14에는 도착 할 수 없다. 하지만 4번 주유소 이전에 2번 주유소를 들렀다 4번 주유소를 가게 되면 총 10의 연료를 얻어서 도착점 14까지 갈 수 있게 된다.

그럼 구현을 어떻게 해야 할까 일단 현재 위치에서 연료를 사용하여 갈 수 있는 모든 주유소의 주유값을 저장해둔다. 그리고 최대값부터 뽑으면서 다음 지점에 갈 수 있는지 확인한다. 만약 갈 수 없으면 다음 최대값을 뽑아서 연료에 더해 다시 다음 지점에 갈 수 있는지 확인한다. 이 과정을 반복하면서 만약 저장된 값이 없는데 다음 지점으로 가지 못한다면 도착점에 갈 수 없다는 뜻이기 때문에 -1을 출력하고 그렇지 않다면 저장된 값에서 하나를 뽑을 때 마다 카운트해서 정답으로 출력하면 된다. 저장된 값이 항상 최대값을 바로 알 수 있어야 하므로 최대힙을 사용하면 빠르게 구할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;


int n, l, p;
pair<int, int> v[10001];
priority_queue<int> pq;

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
	}
	cin >> l >> p;

	sort(v, v + n);
	
	int i = 0, ans = 0;
	bool out = false;

	while (p < l) {
		while (i < n && p >= v[i].first) {
			pq.push(v[i].second);
			i++;
		}

		if (pq.empty()) {
			out = true;
			break;
		}

		p += pq.top();
		pq.pop();
		ans++;
	}

	cout << (out ? -1 : ans);

	return 0;
}