[백준 1826번] [그리디] 연료 채우기

일단 주유소를 거리가 작은 것부터 정렬하고 해당 주유소를 갈 수 있는지 체크해준다.

만약 해당 주유소를 갈 수 있는 연료가 남았다면 일단 통과해주고, 없다면 이전에 있는 주유소 중 연료를 최대한으로 공급할 수 있는 곳을 방문했다고 간주해주면 된다.

 

계속해서 거리가 증가하는 방향으로 이동하고 있는 상황이므로, 결과적으로 모든 주유소를 방문해야 한다.

즉 각 주유소를 통과할 수 있는 연료가 남아 있는지 여부만 지속적으로 Greedy하게 체크해줘도 된다. 이전 주유소를 통과했다면 이전까지 도착하는데에는 연료가 충분했다는 것이므로 현재 주유소를 통과할 만큼의 연료만 있으면 되기 때문이다.

다만, 최소한으로 멈춰야하므로 연료 주입량이 많은 주유소에서 멈추는 것이 가장 이득이다.

 

만약 연료를 공급받지 않은 이전 주유소의 주유량이 필요량보다 적은 경우는 -1을 출력해주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main(void){
    fastio;
    int n;
    cin >> n;
    vector<pii> q;
    for(int i = 0; i < n; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        q.push_back(make_pair(temp1, temp2));
    }
    sort(q.begin(), q.end());
    
    int d, energy;
    cin >> d >> energy;

    int current_pos = 0; // 현재 위치
    int visited_num = 0;
    int current_index = 0;
    
    priority_queue<int> pq;

    while(current_index < n){
        pii next_gas = q[current_index];
        // 연료는 빵빵
        if(energy >= next_gas.first - current_pos){
            pq.push(next_gas.second);
            energy -= (next_gas.first - current_pos);
            current_pos = next_gas.first;
        }
        // 연료 부족
        else{
            while(!pq.empty()){
                energy += pq.top();
                pq.pop();
                visited_num += 1;
                if(energy >= (next_gas.first - current_pos)) break; // 연료 채울만큼 방문
            }
            // 모자라서 끝난 경우
            if(energy < (next_gas.first - current_pos)){
                cout << -1 << "\n";
                return 0;
            }
            else{
                pq.push(next_gas.second);
                energy -= (next_gas.first - current_pos);
                current_pos = next_gas.first;
            }
        }
        current_index++;
    }
    if(current_pos < d){
        // 에너지 충분히 남은 상황
        if(energy >= (d - current_pos)){
            cout << visited_num << "\n";
            return 0;
        }
        else{
            while(!pq.empty()){
                energy += pq.top();
                pq.pop();
                visited_num += 1;
                if(energy >= (d - current_pos)) break;
            }
            if(energy < (d - current_pos)){
                cout << -1 << "\n";
                return 0;
            }
            else{
                cout << visited_num << "\n";
                return 0;
            }
        }
    }
}

p.s) 주유소 거리 순서대로 제공된 줄 알아서 2번 WA나왔다..