[C++] BOJ-1826

 

문제풀이

---

1. 우선순위큐 한개와 pair<int,int>형 배열변수 한개를 선언한다.

 

2. 주유소의 정보가 담겨있는 배열을 오름차순으로 sort한다.

 

3. 현재 가지고있는 연료의 양으로 최대로 갈 수 있는 거리까지의 주유소에서 넣을 수 있는 연료량을 모두 우선순위 큐에 넣는다.

 

4. 우선순위큐의 top에 있는 연료량이 제일 높을 것이므로 top을 트럭에 있는 연료량에 더해준다. 그리고 그때마다 1씩 카운트해준다.

 

5. 트럭에 있는 연료량이 도착범위를 넘어가거나 혹은 우선순위큐가 비어있으면 반복문을 종료한다.

 

6. 마지막으로 트럭에 있는 연료량이 마을에 도착하는데에 충분하다면 cnt를 출력하고 그렇지 않으면 -1을 출력한다.

 

 

1시간 26분

#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, home, cur, idx = 0;
    int cnt = 0;
    
    cin >> N;
    
    pair<int, int> station[N];
    priority_queue<int> pq;
    
    for(int i = 0; i<N; i++){
        cin >> station[i].first >> station[i].second;
    }
    
    sort(station, station+N);
    cin >> home >> cur;
    
    
    while(home > cur){
        while(station[idx].first <= cur){
            if(idx == N)break;
            pq.push(station[idx].second);
            idx++;
        }
        
        if(pq.empty())break;
        cnt++;
        cur += pq.top();
        pq.pop();
    }
    
    if(cur >= home){
        cout << cnt;
    }else{
        cout << -1;
    }
}