연료 채우기 (feat. 백준, 1826번)

연료 채우기
https://www.acmicpc.net/problem/1826

1826번: 연료 채우기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, L, P, cnt = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;   // 거리, 연료양 (거리 오름차순)
    priority_queue<int> fuel;    // 연료양 (내림차순)
    cin >> N;
    for(register int n = 0, a, b; n < N; ++n)
        cin >> a >> b, q.push(make_pair(a, b));
    cin >> L >> P;
    while(P < L){
        while(!q.empty()){
            auto p = q.top();
            if(p.first > P)
                break;
            fuel.push(p.second);
            q.pop();
        }
        if(fuel.empty()){
            cnt = -1;
            break;
        }
        P += fuel.top();
        fuel.pop();
        ++cnt;
    }
    cout << cnt;
    return 0;
}
// *&)*@*

 

이전 "보석 도둑" 과 유사한 문제입니다.

보석 도둑 (feat. 백준, 1202번)

 

1. 현재 보유중인 연료를 기준으로 갈 수 있는 주유소를 모두 수집합니다.
2. 위에서 수집한 주유소 중 가장 연료양이 큰 주유소를 선택합니다.
3. 1,2번을 반복하며 도착점 L에 도달했는지를 확인합니다.