1826번 연료 채우기

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

복습 코테 코딩 Greedy 힙 우선순위큐 그리디 코딩 필수 추천 백준 boj

End : 성경이의 위치에서 마을까지의 거리

oil : 트럭에 원래 있던 연료의 양

#include <bits/stdc++.h>
 
using namespace std;
 
int n, End, oil;
vector<pair<int, int> > v;
priority_queue<int> pq;
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    int a, b;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        v.push_back({ a, b });
    }
 
    sort(v.begin(), v.end());
 
    scanf("%d %d", &End, &oil);
 
    int ans = 0; // 정답
    int here = 0; // 현재 위치
 
    for (int i = 0; i < v.size(); i++) {        
 
        // 현재 위치(here)에서 기름울 충전했음도 못 간다면
        while (!pq.empty() && here + oil < v[i].first)
        {
            // 우선순위 큐에 저장된 기름들을 꺼낸다
            oil += pq.top();
            ++ans;
            pq.pop();
        }
 
        // 이동할 때도 거리만큼 기름을 사용.
        oil = oil - (v[i].first - here);
 
        if (oil < 0) {
            /*
            oil이 음수라는 것은 지금까지 지나오면서 저장한 기름들을
            다 먹었음에도 불구하고 현재 위치(here)에서 도달할 수 없다는 뜻.
            '<='이 아닌 이유는 '딱 맞게' 도착했다는 뜻으로 후에 먹을 수 있는 기름을 저장해야함.
            */
            break;
        }
 
        here = v[i].first;
        pq.push(v[i].second);    
    }
 
    // 나머지 계산
    while (!pq.empty() && here + oil < End)
    {
        oil += pq.top();
        ++ans;
        pq.pop();
    }
 
    printf("%d\n", here + oil >= End ? ans : -1);
 
    return 0;
}