[백준 1826] 연료 채우기 (C++)

1826번: 연료 채우기

 

처음에 DP 문제인줄 알고 DP로 접근을 시도했었다.

dp[현재 이동한 거리][현재 가지고 있는 연료 양] 을 두면 top down DP를 통해서 쉽게 구할 수 있을거라고 생각했었다.

근데 L이 최대 100만이고 연료 양도 최대 100*10000 라서 DP 배열 자체를 할당할 수가 없었다.

 

N과 L이 너무 커서 이건 무조건 그리디라고 생각했고 실제로 그리디로 풀수가 있었다.

 

 

1. 현재 연료를 모두 소진할 때까지 쭉 달린다.

2. 달리는 도중에 주유소를 만나면 priority queue에 저장한다.(최대 힙으로 저장)

3. 연료를 모두 소진하면 priority queue에서 연료를 가져와서 보충한다.

-> 주유소에 들릴때 바로 연료를 충전하지 않고 keep 해놓았다가 나중에 필요할 때 가져오는 방식을 사용한다. 이때 주유소에 들리는 카운터를 +1 해준다.

 

4. 만약 현재 연료가 0가 되었고, priority queue에 저장해 놓은 연료 리스트가 없다면 목표에 도달할 수 없는 것이므로 -1을 출력한다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
int N, L, P;
int info[1000001];
 
void input(){
    cin >> N;
    int a, b;
    for(int i = 0; i < N; i++){
        cin >> a >> b;
        info[a] = b;
    }
    cin >> L >> P;
    
}
 
void solve(){
    priority_queue<int> pq;
    int now_fuel = P;
    int ans = 0;
    
    for(int i = 1; i < L; i++){
        now_fuel--;
        if(info[i]) pq.push(info[i]);
        
        if(!now_fuel){
            if(pq.empty()){
                cout << -1;
                return;
            }
            else{
                ans++;
                now_fuel += pq.top();
                pq.pop();
            }
        }
    }
    
    cout << ans;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}