연료 채우기 1826

문제

접근 방법

주유소마다 들고 간다, 안간다라는 분기로 나눠서 풀면되지 않을까 싶었는데 시간 초과나올 것 같아서 관두었다.
모든 연료를 더 한뒤 낮은거 위주로 빼면 되지 않을까 싶었는데 앞부분이 1, 1, 1,...이런식으로 이루어졌다면 문제가 발생하기에 안된다고 생각했다.
그럼 일단 연료로 갈 수 있는만큼 가고 연료가 부족하면 지나온 정류장에서 연료를 가져왔다는 셈치고 가장 높은 연료를 빼오면 어떨까 싶었다.

3, 5km만큼 떨어진 주유소 2개와 9km 떨어진 마을 그리고 차에는 5km만큼 갈 수 있는 연료가 있다면 5km만큼 간 뒤 4km만큼을 이미 지나온 3, 5km 떨어진 주유소에서 연료를 가져오는 것이다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int N;
    cin >> N;
    vector<pair<int, int>> v;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < N; ++i)
    {
        pair<int, int> j;
        cin >> j.first >> j.second;
        v.push_back(j);
    }
    int L, P, cur = 0, ret = -1;
    sort(v.begin(), v.end());
    cin >> L >> P;
    pq.push({P, 0});
    while (!pq.empty() && cur < L)
    {
        cur += pq.top().first;
        pq.pop();
        ++ret;
        while (!v.empty() && cur >= v.front().first)
        {
            pq.push({v.front().second, v.front().first});
            v.erase(v.begin());
        }
    }
    if (cur < L)
        cout << -1;
    else
        cout << ret;
}

풀이

우선순위 큐를 활용한 문제이다.
해당 거리 내에서 가장 많은 연료를 가져가며 범위를 넓혀가는 것이다.
하지만 함정이 있는데 입력이 정렬된 값이 아니라는 것이다.
항상 조심해야 할 부분인데 항상 놓치는 것 같다.