[BOJ 1826] 연료 채우기

[BOJ 1826] 연료 채우기​

 

우선순위 큐(힙)를 이용해서 그리디로 푸는 문제이다. 우선 주유소를 거리 순으로 정렬한 뒤에, 현재 연료양을 가지고 최대한 갈 수 있는 범위 안에 속하는 주유소들의 연료 양(c)를 모두 최대 힙에 넣는다. 그 다음 힙의 top에서 원소(c)를 하나씩 빼보면서 이 연료를 주입했다면 다음 주유소까지 도달 할 수 있었는지를 확인한다. 만약 불가능 하다면 가능할 때까지 힙에서 원소를 계속 빼서 더해본다. 만약 모두 뺐는데도 다음 주유소까지 도달할 수 없다면 이는 불가능하다는 뜻이므로 -1을 출력하면 된다. 

 

 

 

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
#define SIZE 10009
struct Oil{
    int d,c;
 
    Oil(){}
    Oil(int _d,int _c){
        d=_d;
        c=_c;
    }
    const bool operator<(const Oil &o) const{
        return d<o.d;
    }
};
priority_queue<int> pq;
int n;
Oil o[SIZE];
int main(){
    scanf("%d",&n);
 
    for(int i=0 ; i<n ;i++){
        int a,b;    scanf("%d %d",&a,&b);
        o[i]=Oil(a,b);
    }
 
    int dest,init;    scanf("%d %d",&dest,&init);
 
    sort(o,o+n);
 
    int cur=init,ans=0,idx=0;
 
    while(cur<dest){
        for( ; cur >= o[idx].d ; idx++){
            pq.push(o[idx].c);
        }    
 
        while(cur < o[idx].d && cur<dest){
            int top=pq.top();    pq.pop();
            cur+=top;
            ans++;
 
            if(pq.size()==0 && cur<o[idx].d){
                printf("-1\n");
                return 0;
            }
        }
    }
    printf("%d\n",ans);
 
    return 0;
}