문제 출처

1. 문제설명

  • 트럭을 정글 속에서 운전하다가 1km를 가는데 1L의 연료가 새 나가게 된다.
  • 중간중간에 연료를 채울 수 있는 주유소가 N개 있다.
  • 주유소에서 멈추는 횟수를 최소화 하려고 한다.
  • 주유소에서 멈추는 횟수를 출력하라.



2. 알고리즘 설계

  • 그리디 문제이다.
  • 주어진 주유소의 위치와 주유량을 순차적으로 저장한다.
  • 주유소의 위치가 적은 순으로 정렬한다.
  • 현재의 연료량이 주유소의 위치보다 크다면 연료 저장 후 건너뛰고,
  • 아니라면, 저장된 연료 중 가장 양이 많은 주유소에서 주유한다.



3. 로직

  • 도착 지점을 벡터의 n번째 위치에 넣어준다.
    • 0으로 초기화 되어 있으므로, 연료 부분은 따로 건드리지 않아도 된다.
  • 도착 지점이 적은 순으로 정렬한다.
  • 정렬된 도착 지점을 하나씩 살피는데,
    • 도착 지점보다 연료가 여유가 있으면, 해당 주유소의 연료량이 큰 순으로 저장한다.
    • 도착 지점보다 연료가 여유가 없으면, 미리 저장된 연료에서 가장 큰 연료를 추가한다.
      • 그리고 방문횟수를 1회 카운팅한다.
  • 만약 연료가 필요한데 미리 저장된 연료가 없다면,
    • 도착지점까지 갈 수 없다는 뜻이다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

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

	int n, fuel, ans = 0; 
	cin >> n;
	vector<pii> v(n+1);
	priority_queue<int> pq;

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

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

	for (int i = 0; i <= n; i++) {
		while (fuel < v[i].first) {
			if (pq.empty()) {
				cout << -1;
				return 0;
			}

			fuel += pq.top();
			pq.pop();
			ans++;
		}

		pq.push(v[i].second);
	}

	cout << ans;
	return 0;
}



5. 소감

  • 도착 지점을 우선순위 큐에 넣으니 구현이 매우 깔끔해졌다.
  • 도착 지점을 굳이 검사하지 않아도, n만큼 루프를 돌면 종료하게 되기 때문이다.