Logo냥냠감자기술 블로그
Skip to Content
AlgorithmGreedy (14)연료채우기
작성일: 2024-01-12

문제

백준 1826 - 연료채우기 

  • 난이도: 골드2
  • 알고리즘: 그리디, 우선순위큐

코드

#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin>>n; vector<pair<int, int>> infos(n); for(int i=0; i<n; i++) { cin>>infos[i].first>>infos[i].second; } sort(infos.begin(), infos.end()); int target, currFuel; cin>>target>>currFuel; int infoIndex=0; priority_queue<int> pq; int cnt=0; while(currFuel<target) { while(infoIndex<infos.size() && currFuel>=infos[infoIndex].first) { pq.push(infos[infoIndex].second); infoIndex++; } if(pq.empty()) { break; } currFuel+=pq.top(); pq.pop(); cnt++; } if(currFuel<target) { cout<<-1; } else { cout<<cnt; } }

회고

문제를 보자마자 우선순위 큐를 이용하면 쉽게 해결할 수 있겠다는 생각이 들었다. 그에 비해 우선순위 큐를 자주 사용해보지 않아서 그런지 구현은 조금 더 여려웠던 것 같다. 그래도 나름 쉽게 해결한 것 같아 성취감이 든다