[백준/BOJ] 1826. 연료 채우기 [Gold 3]

1826. 연료 채우기

문제출처 : https://www.acmicpc.net/problem/1826

code

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

int main()
{
	int N, i, L, P, cnt = 0;
	cin >> N;
	vector<pair<int, int>> v(N+1);
	priority_queue<int> pq_gas;
	bool ispossible = true;


	for (i = 0; i < N; i++)
		cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());
	cin >> L >> P;

	for (i = 0; i <= N; i++)
	{
		if (ispossible)
		{
			if (v[i].first <= P)
			{
				pq_gas.push(v[i].second);
			}
			else
			{
				while (v[i].first > P)
				{
					if (pq_gas.empty())
					{
						ispossible = false;
						break;
					}
					P += pq_gas.top();
					pq_gas.pop();
					cnt++;
				}
				i--;
			}
		}
		else
			break;
	}
	while (L > P)
	{
		if (pq_gas.empty())
		{
			ispossible = false;
			break;
		}
		P += pq_gas.top();
		pq_gas.pop();
		cnt++;
	}
	if (ispossible)
		cout << cnt;
	else
		cout << -1;

	return 0;
}

앞서 풀어본 공주님 정원가꾸기랑 선분겹치기랑 비슷한 문제였다. 이것역시 선분겹치는 부분을 최소화하는 방법으로 풀면된다. 그리고 가능 여부는 boolean값으로 설정해서 판단하게했다.

주의할점은
입력에서 주유소의 위치가 정렬되지 않기때문에 정렬을 한번 해줘야한다.