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

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

1826번: 연료 채우기

골드3치고는 풀이법이 그렇게 어렵지 않다고 느꼈다.

​

1. 우선 문제의 입력들을 받은 뒤, 오름차순으로 정렬해준다.

2. 현재 연료량 만큼 전진한다. 연료를 1씩 감소시키며 전진하다가 주유소를 만나면 해당 주유소에서 주유 가능한 연료량을 우선 순위 큐에 저장한다!

3. 연료가 0이 되는 순간, 큐에서 제일 앞에 있는 놈(주유 가능한 연료가 제일 많은 놈)만큼 주유한다! 그리고 당연히 사용한 주유소는 큐에서 지워준다.

※ 연료가 0이 되는 순간에 큐가 비어있다면, 주유가 불가능하므로 -1를 출력해주면 된다.

for문을 목적지에 도달하기 직전까지 돌렸기 때문에 아무탈 없이 for문을 종료하면 목적지에 도달가능하다는 의미가 된다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,a,b;
int dist, fuel;

vector<pair<int,int>> v;
priority_queue<int> pq;

bool cmp(pair<int,int> a, pair<int, int> b){
    if(a.first==b.first){
        return a.second > b.second;
    }
    return a.first < b.first;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;

    for(int i=0; i<n;i++){
        cin >> a >> b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end(),cmp);

    cin >> dist >> fuel;

    int ans=0,idx=0;
    for(int i=1; i<dist;i++){
        fuel--;
        if(v[idx].first==i){
            pq.push(v[idx].second);
            idx++;
        }
        if(fuel<=0){
            if(!pq.empty()) {
                fuel = pq.top();
                pq.pop();
                ans++;
            }
            else{
                ans = -1;
                break;
            }
        }
    }

    cout << ans;
    return 0;
}