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

www.acmicpc.net/problem/1826

1826번: 연료 채우기

 

 

 

알고리즘 종류

우선순위 큐

 

 

 

사고 과정

우선순위 큐 2개를 이용해서 해결했습니다. 현재 가진 연료로 갈 수 있는 거리까지 이동하고, 이 후에 나타난 주유소까지 도달하기 위한 연료를 지나친 주유소에서 가장 연료를 많이 주는 주유소를 선택하는 방법으로 해결했습니다.

 

1. 우선순위 큐(pq1)에 주유소 위치와 연료를 저장합니다. 주유소의 주유소의 위치를 기준으로 최소 힙을 만듭니다.

2. 또 다른 우선순위 큐(pq2)를 만듭니다. 이곳에서 지나친 주유소가 제공하는 연료를 저장합니다. 최대 힙으로 만듭니다.

 

3. 현재 가진 연료로 갈 수 거리를 초과한 주유소를 우선순위 큐에서 찾습니다. 찾을 때까지 우선순위 큐에서 pop()한 주유소들은 pq2에 넣습니다.

4. pq2에서 연료를 꺼내보면서 초과한 주유소를 지나칠 수 있을 때까지 pop()하여 꺼냅니다. 동시에 개수를 셉니다.

5. 3번 4번을 반복합니다.

 

6. 목적지에 도착하지 못하는 경우는 다음과 같습니다.

    6-1. 모든 주유소를 다 들려도 목적지에 도착하지 못하는 경우

    6-2. 현재 가진 연료로 다음 주유소에 도착하지 못하는 경우

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
 
using namespace std;
 
int n;
int e, right;
int cnt = 0;
 
bool flag = false;
 
priority_queue<pair<int, int> > pq1; // 주유소의 위치와 연료로 갈 수 있는 거리를 저장. 최소 힙  
priority_queue<int> pq2; // 주유소에서 제공하는 연료량. 최대 힙  
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    int a, b;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        pq1.push({-a, (a+b)});
    }
    
    cin >> e >> right;
 
    while(true){
        
        // 목적지 도착  
        if(right >= e) {
            flag = true;
            break;
        }
        
        // 모든 주유소에 멈춰도 도착하지 못함  
        if(pq1.empty()){
            flag = false;
            break;
        }
        
        int next_station;
        while(!pq1.empty()){
            if(right < -pq1.top().first){
                next_station = -pq1.top().first;
                break;
            }
            pq2.push(pq1.top().second + pq1.top().first);
            pq1.pop();
        }
        
        // 가진 연료로 다음 주유소 도착 못함  
        if(pq2.empty()) {
            flag = false;
            break;
        }
        
        while(!pq2.empty()){
            right += pq2.top();
            pq2.pop();
            cnt++;
            if(right >= next_station) break;
        }
    }
    
    if(flag) cout << cnt << endl;
    else cout << -1 << endl;
}

 

 

 

시행착오