BOJ1826.md

문제

연료 체우기

문제 원본

문제의 원본은 여기서 확인하세요.

분류

• 그리디 알고리즘
• 우선순위 큐

풀이

현재 연료로 방문할 수 있는 주유소를 우선 순위 큐에 넣고, 이중에 최대의 연료를 가진 주유소를 택해 방문한다. 마을에 도착 하지 못하였지만 더이상 방문할 주유소가 없는 경우 -1

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdlib.h>

using namespace std;

class GasStation {
public:
    int distance;
    int amount;

    bool operator<(GasStation& station) {
        return station.distance > this->distance;
    }
};



void solve(vector<GasStation> &stations, int distance, int amount) {
    sort(stations.begin(), stations.end());

    int count = 0;

    int i = 0;
    priority_queue<int> pq;

    while (amount < distance) {
        while ((i < stations.size()) && stations[i].distance <= amount) {
            pq.push(stations[i++].amount);
        }

        if (pq.empty()) {
            count = -1;
            break;
        }

        amount += pq.top();
        pq.pop();
        count++;
    }

    cout << count << endl;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N, amount, distance;
    
    cin >> N;
    vector<GasStation> stations(N);

    for (int i = 0; i < N; i++) {
        cin >> stations[i].distance >> stations[i].amount;
    }
    cin >> distance >> amount;

    solve(stations, distance, amount);

    return 0;
}