[백준] C++ 연료채우기(1826)

이 문제의 목적은 목적지까지 주유소를 최대한 적게 방문하는 것이다.

 

어떻게 하면 최대한 적게 방문하고 목적지까지 갈 수 있을까??

사고를 좀 거꾸로 할 필요가 있다.

 

우선 트럭을 타고 길을 지나간다.

가는 길에 주유소가 있었다면 주유소에 대한 정보를 저장한다.

길을 가다 보면 연료가 바닥난다.

연료가 바닥이 났을 때 이전에 저장했던 주유소 중 가장 연료가 많이 저장된 곳에서 주유를 한다.(주유를 하고 난 후 pop)

이러한 방법으로 목적지까지 도달하는 것이 가능하다면 주유소에서 멈추는 횟수를 출력하고

그렇지 않다면 -1을 출력한다.

 

즉 방문하면서 주유하는 것이 아닌 연료가 바닥으로 떨어졌을 때 이전 주유소에 대한 정보를 가지고 주유하는 것이 핵심이다.

 

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;
priority_queue<int>pq;
unordered_map<int, int>hashMap;
int main(void)
{
	int N = 0;
	cin >> N;

	int num1 = 0;
	int num2 = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> num1 >> num2;
		hashMap[num1] = num2;
	}

	int end = 0;
	int count = 0;

	cin >> end >> count;

	int i = 0;
	int result = 0;
	while (true)
	{
		if (i == end)
		{
			break;
		}
		if (hashMap[i] != 0)
		{
			pq.push(hashMap[i]);
		}

		if (count == 0)
		{
			if (!pq.empty())
			{
				count += pq.top();
				pq.pop();
				result++;
			}
			else
			{
				result = -1;
				break;
			}
		}
		count--;
		i++;
	}

	cout << result;

	return 0;
}