[ 백준 2109 ] 순회강연 (C++) - 그리디, 우선순위큐

---

🔗 문제 링크

2109번: 순회강연

---

💡 문제 풀이 및 해석

일단, 보자마자 비싼 강의를 최대한 많이 들어야 한다는 것을 알 수 있다. 여기서 어떻게 들어야 할 것인가가 중요하다. 여기서 day로 정렬해서 한다면, 문제가 발생한다. 예를 들어서, 같은날 비싼 2개의 강의가 있을 때, 전날 강의를 버리고 그 다음날까지 유예기간이 있는 강의를 들을 수가 없기 때문이다. 여기서 해결방법으로는 아래와 같다.

1. 가장 비싼 강의로 내림차순으로 정렬한다.
2. 유예기간이 3일인 강의가 있다면, 3일에 강의일정이 있는지 확인한다.
   2-1. 강의일정이 없다면, 등록한다.
   2-2. 강의일정이 있다면, 그 전날에 강의일정이 있는지 확인하다. (있을 때까지 반복)
   2-3. 만약, 1일까지 강의일정이 꽉차있다면 이 강의는 버린다. 그리고 앞으로 유예기간이 3일 이하는 검사할 필요가 없다.
3. 이렇게 모든 강의를 검사하면 벌 수 있는 최대값이 나온다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<queue>

using namespace std;

priority_queue<pair<int, int>> q;

int n;
bool visit[10001];

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int cost, day; cin >> cost >> day;
        q.push({ cost,day });
    }
}

int sol() {
    int answer = 0;
    int pass = 0;
    while (!q.empty()) {
        int cost = q.top().first, day = q.top().second; q.pop();
        if (day < pass) continue;
        for (int i = day; i > 0; i--) {
            if (!visit[i]) {
                visit[i] = true;
                answer += cost;
                break;
            }
            if (i == 1) pass = day;
        }
    }
    return answer;
}

int main() {
    input();
    cout << sol();
    return 0;
}

---

🤔 문제 후기

솔직히, 내가 생각한대로 풀지 못했다. 시간초과는 나지 않지만 visit을 체크하는 방법보다는 union_find 방식으로 분리집합 알고리즘을 사용해서 하면 N의 범위가 1억이 넘어가도 O(N)으로 끝낼 수 있을 것이다. 이 문제는 범위가 크지 않고, 시간도 비교적 널널 했으므로 일단, 이런 방식으로 풀어놨지만, 나중에 분리집합을 연습할 겸 다시 풀어봐야겠다.