BOJ 1826 연료 채우기

이 문제의 접근 방법은 현재 가진 연료로 갈수 있는 주유소 중 멈췄을때 가장 많은 연료를 획득할 수 있는 주유소에서 멈추면 된다. 주유소의 위치가 순서대로 들어오지 않기 때문에 주유소 위치를 정렬 시켜주어야 한다.

 

이후 현재 가진 연료로 멈출 수 있는 모든 주유소에서 얻을 수 있는 연료의 양을 우선순위 큐에 넣고 빼면서 전체 획득한 연료 양을 누적시킨다.

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

priority_queue<int> pq;
vector<pair<int, int>> v;
int n;
int l, p;

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

	
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());
	
	cin >> l >> p;

	int curP = 0, curL = p, ans = 0;
	while(curL < l)
	{
    	// curP는 주유소의 인덱스를 나타내고 주유소의 위치가 현재 가지고있는 연료로 도착 할 수 있는 경우
        // 얻을 수 있는 연료를 PQ에 넣어준다.
		while(curP < n && v[curP].first <= curL)
		{
			pq.push(v[curP++].second);
		}
		if(pq.empty())
		{ // L 에 도착도 못했고, 더 이상 갈 곳도 없음.
			ans = -1;
			break;
		}
		curL += pq.top();// 획득한 연료 누적시켜준다.
		pq.pop();
		ans++;
	}
	cout << ans << '\n';
	return 0;
}