[C++] 백준 1826번: 연료 채우기

문제 링크

1826번: 연료 채우기

문제 요약

L에 위치한 마을까지 가는데, 연료가 1km당 1L씩 소모된다. 트럭이 출발할때는 P만큼의 연료가 들어있다. 마을로 가는 경로 중간중간에 주유소가 위치한다. 주유소의 위치와 주유소에서 채울 수 있는 연료가 주어질 때, 마을까지 도착하는데 주유소에 정차해야하는 최소 횟수를 구해야 한다.

접근 방법

그리디하게 접근했습니다. 현재 연료로 방문할 수 없는 주유소를 만날때마다, 지나쳤던 주유소 중에 가장 연료를 많이 넣을 수 있었던 주유소를 방문하는 식으로 처리를 해주었습니다.

먼저 주유소의 위치와 넣을 수 있는 연료를 pair로 묶어 벡터에 저장해줍니다. 이 벡터를 주유소 위치를 기준으로 오름차순으로 정렬합니다. 이제, 현재 연로로 갈 수 있는 최대 거리까지 이동을 합니다. 이동 도중에 만나는 주유소들은 모두 우선순위큐에 저장해줍니다. 이 우선순위큐는, 넣을 수 있는 연료의 양을 기준으로 내림차순으로 정렬됩니다.

만약 다음 주유소를 현재 연료로 방문할 수 없다면, 우선순위큐에서 하나씩 빼서, 연료에 더해줍니다. 만약 우선순위큐가 비었음에도 다음 주유소를 방문할 수 없다면 -1을 출력하고 종료해줍니다.

이런식으로 목적지까지 도착할 때, 우선순위큐에서 pop을 한 횟수를 출력해주면 됩니다.

생각한 로직이 제대로 들어맞아서 기분좋게 한번에 AC를 받았습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Compare {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second < b.second;
	}
};

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
	return a.first < b.first;
}

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

	int n, l, p;
	cin >> n;

	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;

	cin >> l >> p;

	v.push_back({ l, 0 });
	sort(v.begin(), v.end(), compare);

	int cnt = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
	for (auto& i : v) {
		if (p >= l)
			break;

		if (p > i.first) {
			pq.push(i);
		}
		else {
			while (p < i.first) {
				if (pq.empty()) {
					cout << -1 << '\n';
					return 0;
				}

				p += pq.top().second;
				pq.pop();
				cnt++;		
			}
			pq.push(i);
		}
	}

	cout << cnt << '\n';
	return 0;
}