[PS] 백준 2109번 순회강연

이번에는 백준 2109번 순회강연 문제를 풀어보았습니다.

처음에는 날짜별로 어떤 강연을 선택할지 하나씩 결정해야 하나 생각했습니다.

하지만 마감일이 빠른 강연부터 처리하면서 현재까지 선택한 강연 중 가장 강연료가 작은 것만 제거하면 항상 최적의 선택을 유지할 수 있다는 점을 이용하여 해결하였습니다.

이를 위해 마감일 기준 정렬과 우선순위 큐를 함께 사용하였습니다.

---

문제 설명

각 대학은

• 강연료 p
• 마감일 d

를 제시합니다.

하루에 하나의 강연만 할 수 있을 때, 받을 수 있는 강연료의 최댓값을 구하는 문제입니다.

---

풀이 아이디어

먼저 모든 강연을 마감일 기준으로 오름차순 정렬하였습니다.

이후 현재 강연료를 우선순위 큐에 넣었습니다.

현재까지 선택한 강연의 개수가 현재 마감일보다 많아진다면, 선택한 강연 중 강연료가 가장 작은 강연을 제거하였습니다.

이 과정을 반복하면 항상 현재까지 가능한 강연들 중 가장 큰 강연료만 남게 됩니다.

마지막에 우선순위 큐에 남아있는 강연료를 모두 더하여 정답을 구하였습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int, int>> inp;

    for (int i = 0; i < n; i++) {
        int p,d;
        cin >> p >> d;
        inp.push_back({d,p});
    }

    sort(inp.begin(), inp.end());

    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto [d, p] : inp) {
        pq.push(p);

        if (pq.size() > d) {
            pq.pop();
        }
    }

    int ret = 0;

    while(!pq.empty()) {
        ret += pq.top();
        pq.pop();
    }

    cout << ret << '\n';

    return 0;
}

---

풀이 흐름

1. 모든 강연 정보를 입력받습니다.
2. 마감일 기준으로 오름차순 정렬합니다.
3. 현재 강연료를 우선순위 큐에 넣습니다.
4. 현재 선택한 강연 개수가 마감일을 초과하면 가장 작은 강연료를 제거합니다.
5. 모든 강연을 처리한 뒤 우선순위 큐에 남아있는 강연료를 더합니다.
6. 결과를 출력합니다.

---

구현 포인트

1. 마감일 기준 정렬

강연을 마감일 기준으로 오름차순 정렬하였습니다.

sort(inp.begin(), inp.end());

벡터에는

{마감일, 강연료}

형태로 저장하였기 때문에 마감일 기준으로 자동 정렬됩니다.

---

2. 최소 힙 사용

현재 선택한 강연료를 최소 힙으로 관리하였습니다.

priority_queue<int, vector<int>, greater<int>> pq;

가장 작은 강연료를 빠르게 제거하기 위해 최소 힙을 사용하였습니다.

---

3. 현재 강연 추가

현재 강연은 우선 선택한다고 가정하고 우선순위 큐에 넣었습니다.

pq.push(p);

이후 현재 선택이 가능한지 확인하였습니다.

---

4. 선택 가능한 개수 초과 시 제거

현재까지 선택한 강연 개수가 현재 마감일보다 많아진다면,

모든 강연을 수행할 수 없다는 의미입니다.

if (pq.size() > d) {
    pq.pop();
}

가장 강연료가 작은 강연을 제거하여 항상 더 큰 강연료를 남기도록 하였습니다.

---

5. 최종 강연료 계산

모든 강연을 처리한 뒤 우선순위 큐에는 수행할 강연만 남게 됩니다.

while(!pq.empty()) {
    ret += pq.top();
    pq.pop();
}

남아있는 강연료를 모두 더하여 최대로 벌 수 있는 금액을 계산하였습니다.