Skip to content

Latest commit

ย 

History

History
80 lines (58 loc) ยท 1.6 KB

File metadata and controls

80 lines (58 loc) ยท 1.6 KB

๋ฌธ์ œ

์—ฐ๋ฃŒ ์ฒด์šฐ๊ธฐ

๋ฌธ์ œ ์›๋ณธ

๋ฌธ์ œ์˜ ์›๋ณธ์€ ์—ฌ๊ธฐ์„œ ํ™•์ธํ•˜์„ธ์š”.

๋ถ„๋ฅ˜

  • ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • ์šฐ์„ ์ˆœ์œ„ ํ

ํ’€์ด

ํ˜„์žฌ ์—ฐ๋ฃŒ๋กœ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ฃผ์œ ์†Œ๋ฅผ ์šฐ์„  ์ˆœ์œ„ ํ์— ๋„ฃ๊ณ , ์ด์ค‘์— ์ตœ๋Œ€์˜ ์—ฐ๋ฃŒ๋ฅผ ๊ฐ€์ง„ ์ฃผ์œ ์†Œ๋ฅผ ํƒํ•ด ๋ฐฉ๋ฌธํ•œ๋‹ค. ๋งˆ์„์— ๋„์ฐฉ ํ•˜์ง€ ๋ชปํ•˜์˜€์ง€๋งŒ ๋”์ด์ƒ ๋ฐฉ๋ฌธํ•  ์ฃผ์œ ์†Œ๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ -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;
}