연료 채우기(Greedy)

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

1826번: 연료 채우기

 

이전에 풀었던 컵라면 문제와 맥락이 비슷한 그리디 문제다.

https://djgameprogramming.tistory.com/47

 

1. 주유소들을 위치 기준으로 오름차순 정렬해준다.

2. 현재 연료로 갈 수 있는 주유소들의 연료의 양을 우선순위 큐(내림차순)에 전부 삽입한다.

    ->우선순위 큐의 top은 현재 갈 수 있는 주유소 중 가장 연료를 많이 주는 주유소.

3. 우선순위 큐의 top을 현재 연료에 추가하고 출력값을 +1 해준다.

4. 현재 연료가 도착지보다 크거나 같아질때까지 2, 3번을 반복한다.

5. 4번을 만족하기 전에 우선순위 큐가 비게된다면 도달할 수 없으므로 -1을 출력해야 한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cmd;
	cin >> cmd;

	vector<pair<int, int>> vec;
	while (cmd--)
	{
		int a, b;
		cin >> a >> b;
		vec.push_back(pair<int, int>(a, b));
	}

	int dest, gas;
	cin >> dest >> gas;

	sort(vec.begin(), vec.end());

	priority_queue<int, vector<int>, less<int>> pq;

	int ret = 0;
	int index = 0;
	while (gas < dest)
	{
		while (index < vec.size() && vec[index].first <= gas)
		{
			pq.push(vec[index].second);
			index++;
		}
		if (pq.empty())
		{
			// 실패
			cout << -1 << '\n';
			return 0;
		}
		else
		{
			gas += pq.top();
			pq.pop();
			ret++;
		}
	}

	cout << ret << '\n';
}