C++ / 백준 / 1826 / 연료 채우기

문제

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

1826번: 연료 채우기

 

문제풀이

트럭이 주유소에 도착할 때마다 멈춰야 하는지를 판별하는 것이 아닌, 되돌리기를 한다고 생각하면 된다.

현재 위치에서 갈 수 있는 최대 위치를 구하고, 그 사이의 주유소 중에서 가장 많은 연료를 얻을 수 있는 주유소에 간다.

우선순위 큐를 이용해 갈 수 있는 주유소를 연료의 양 기준으로 내림차순으로 하여 가장 많은 연료를 채운다.

 

먼저 입력받은 주유소 정보를 벡터에 저장하고, 오름차순으로 정렬을 한다.

loc변수는 최종 목적지인 마을 위치를, gas변수는 현재 가스의 양을 저장한다.

gas는 최대로 갈 수 있는 위치를 나타내기도 한다.

 

목적지에 도달 못했을 때, 우선순위 큐가 비어있다면 가진 기름으로 주유소를 갈 수 없으므로 while문을 종료한다.

우선순위 큐가 비어있지 않다면 주유소를 갈 수 있으므로 멈춘 횟수를 1 더하고, gas에 주유소 기름을 더하고, pop을 하여 다녀간 주유소 정보를 삭제한다. 목적지에 도착하거나 (gas >= loc), 더 갈 주유소가 없다면(pq.empty()) -1을 출력한다.

 

코드

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

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

	long long N(0), idx(0), gas(0), loc(0), answer(0);

	cin >> N;

	vector<pair<long long, long long>>gs(N, { 0,0 });
	priority_queue<long long>pq;

	for (idx = 0; idx < N; ++idx) {
		cin >> gs[idx].first >> gs[idx].second;
	}

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

	cin >> loc >> gas;

	idx = 0;

	while (gas < loc) {
		for (idx; idx < N; ++idx) {
			if (gas >= gs[idx].first) {
				pq.push(gs[idx].second);
			}
			else break;
		}
		if (pq.empty()) {
			break;
		}
		else if (!pq.empty()) {
			answer++;
			gas += pq.top();
			pq.pop();
		}

	}
	if (gas >= loc) {
		cout << answer;
		return 0;
	}
	else cout << "-1";
}