(BOJ) 2109 순회강연

문제: https://www.acmicpc.net/problem/2109

문제 풀이:

각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다.

ex)

2

1 10  일 때

꼭 10일에 강연을 하는 것이 아니라 10일 안에만 강연을 하면 됨

- 입력받은 값들은 vector에 넣어준다 {날짜, 금액}

- 날짜가 빠르고 금액이 큰 순으로 정렬한다.  (어차피 다 볼거니까 날짜만 빠르게 정리하면 됨)

- 벡터 순서대로 보면서 일단 sum+=v[i].second, pq.push(v[i].second) 함

  현재 강연 마감일(v[i].first)이 지금껏 강연한 수(pq.size())보다 작으면  sum-=pq.top();

소스코드:

#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int n,cur,sum; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; vector<pair<int, int>> v;   for (int i = 0; i < n; i++) { int money, day; cin >> money>> day; v.push_back({ day,-money }); } sort(v.begin(), v.end()); priority_queue<int> pq; for (int i = 0; i < n; i++) { sum -= v[i].second; pq.push({ v[i].second }); if (v[i].first < pq.size()) { sum += pq.top(); pq.pop(); } } cout << sum; return 0; }