์ฐ๋ฃ ์ฒด์ฐ๊ธฐ
๋ฌธ์ ์ ์๋ณธ์ ์ฌ๊ธฐ์ ํ์ธํ์ธ์.
- ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ
- ์ฐ์ ์์ ํ
ํ์ฌ ์ฐ๋ฃ๋ก ๋ฐฉ๋ฌธํ ์ ์๋ ์ฃผ์ ์๋ฅผ ์ฐ์ ์์ ํ์ ๋ฃ๊ณ , ์ด์ค์ ์ต๋์ ์ฐ๋ฃ๋ฅผ ๊ฐ์ง ์ฃผ์ ์๋ฅผ ํํด ๋ฐฉ๋ฌธํ๋ค. ๋ง์์ ๋์ฐฉ ํ์ง ๋ชปํ์์ง๋ง ๋์ด์ ๋ฐฉ๋ฌธํ ์ฃผ์ ์๊ฐ ์๋ ๊ฒฝ์ฐ -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;
}