BOJ 1826 - 연료 채우기

www.acmicpc.net/problem/1826

1826번: 연료 채우기

 

이 문제는 그리디 방식으로 풀어야 하는문제다

왜냐면, 가지고 있는 연료의 양이 제한적이고, 주유소를 최소한으로 방문해야 하기 때문이다.

 

정렬의 기준은 현 위치에서 주유소 까지의 거리가 가까운 순서대로 정렬한다

그리고 목적지 까지의 거리(L) 와 현재 보유하고 있는 연료량(P) 을 비교했을때, P 가 더 적은 경우 주유소를 방문해서 충전을 해야만한다.

그리고 우선순위 큐(최대힙) 을 만들어서, 방문 하는 주유소에서의 주유량을 최대힙 정렬한다.

(우선순위 큐를 쓰는 이유는 N 의 최대가 만 이기 때문에, 단순히 이중 포문으로 하나하나 비교하면 시간 초과 되므로)

 

최대 주유량만 빼내오면서 거리를 갱신하면 굳이 방문하지 않아도될 주유소를 건너뛸 수가 있다.

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
int N, answer;
int L, P; // 마을까지 거리, 기존 연료량 
vector<pair<int, int>> gas_station; // 주유소 까지 거리, 채울 수 있는 연료량 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        gas_station.push_back({a, b});
    }
    
    cin >> L >> P;
    
    sort(gas_station.begin(), gas_station.end()); // 주유소 까지 거리 기준 오름차순
    
    priority_queue<int> pq;
    
    // 현재 인덱스, 가지고 있는 연료량
    int idx = 0, cur_gas = P;
    
    while(cur_gas < L) { // 목적지 거리보다 연료량이 적으면 주유소 가야됨 
        while(idx < N && gas_station[idx].first <= cur_gas) {
            pq.push(gas_station[idx].second);
            idx++;
        }
        
        if (pq.empty()) { // 더 이상 갈 수 없을때 
            answer = -1;
            break;
        }
        
        cur_gas += pq.top();
        pq.pop();
        answer++;
    } 
    
    cout << answer;
    
    return 0;
}