BOJ 2109 : 순회강연

풀이요약

우선순위 큐

풀이상세

1. 문제는 해당 일을 줄 경우, 그 안에 와서 강연을 했을 때 받을 수 있는 최대 강연료를 찾는 것이다. 즉, 예를 들어 1,20 , 2,10 , 3,50 , 3,40 , 3,30 인 경우 최대 강연료는 120 이 된다.

2. 먼저 입력값을 일 순으로 오름차순 정렬한 후, 우선순위 큐의 사이즈를 하나의 day로 가장하자. 만약 임의의 날짜가 우선순위 큐의 사이즈 보다 크다면, 우선순위 큐가 담고 있는 비용 중 가장 작은 값을 빼주자. 이를 위해 우선순위 큐를 오름차순 정렬로 해두자.

3. 이러한 방식을 통해 최종적으로 주어진 날짜 안에서 구할 수 있는 최대의 비용들만 우선순위 큐에 남는다. 이를 모두 더한 값이 답이 된다.

배운점

• cpp 의 경우 while 문에 {} 블록이 없다면, 반복문이 종료되지 않더라.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N, ans;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    int d, p;
    for (int i = 0; i < N; i++) {
        cin >> p >> d;
        v.push_back({d, p});
    }
    sort(v.begin(), v.end());
}

void solve() {
    for (int i = 0; i < N; i++) {
        pq.push(v[i].second);
        if (pq.size() > v[i].first) pq.pop();
    }
    while (!pq.empty()) {
        ans += pq.top(); pq.pop();
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve();
    output();
}