백준 1826 (연료 채우기) / C++

문제링크 : 1826번: 연료 채우기 (acmicpc.net)

1826번: 연료 채우기

 

> 풀이

 

입력받은 거리 / 연료 값을 거리 순으로 정렬한다

 

남은 연료 대비 갈 수 있는 주유소들을 우선순위 큐(최대 힙)에 저장 -> 다음 주유소에 도착할 수 있을 때까지 우선순위 큐에서 주유소를 빼냄(빼내는 횟수 카운트) -> 연료 총합이 목표거리에 도달할 때까지 반복

 

#include <bits/stdc++.h>
using namespace std;


priority_queue<int, vector<int>, less<int> >pq;
pair<int, int> fuel[10000];
int N, L, P, cnt;

int main(void) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
                scanf("%d %d", &fuel[i].first, &fuel[i].second);
        }
        sort(fuel, fuel + N);
        
        scanf("%d %d", &L, &P);

        int idx = 0;
        while (L > P) {
                while (fuel[idx].first <= P && idx < N)
                        pq.push(fuel[idx++].second);
                
                if (!pq.empty()) {
                        P += pq.top(), pq.pop();
                        cnt++;
                }
                else if (idx == N || fuel[idx].first > P) {
                        cnt = -1;
                        break;
                }
        }

        printf("%d", cnt);
        return 0;
}