[C++] 백준 2109 순회강연 [Gold3]

풀이

1. 강연까지 남은 날짜 d와 강연료 p가 주어졌을 때 최대 이익을 얻도록 강의를 스케쥴링 하는 문제이다.

2. 강연 날짜를 1, 2, 3 순으로 세어가는 것이 아니라 3, 2, 1 순으로 거꾸로 세어가는 것이 필요하다.

3. 3일째 날에 할 수 없는 강연은 1, 2일 안에 와서 해달라고 한 강연들이다.

4. 또한, 2일째 날에 할 수 없는 강연은 1일 안에 와서 해달라고 한 강연이고, 2,3일 내에 와서 해달라고 한 강연은 할 수 있다.

4. 이때, 2일 내에 할 수 있는 강연보다 3일 내에 할 수 있는 강연이 강연료가 더 크다면 그걸 선택하면 된다.

알고리즘

1. 날짜-강연료 벡터를 날짜기준 내림차순 정렬한다.

2. 이때, 날짜의 max값을 저장해 놓는다.

3. 2 중 for loop (i) 을 순회하는데, 첫 번째 loop에서는 날짜의 최대값에서부터 거꾸로 접근해간다.

4. 두번째 loop (j) 에서는 해당 날짜에서 할 수 없는 강연들을 제외하고 모두 우선순위 큐에 push 한다.

5. 이때 할 수 없는 강연은 v[j].d < i 인 강연이다. 왜냐면 i=3일때 v[j].d=2라면 해당 강의는 2일 안에 와서 했어야 하는 강의이기 때문에 3일째에서는 할 수 없는 강의다.

6. j 는 바깥쪽에서 정의했기 때문에, 다음 i loop에서는 break 된 지점부터 시작해서 for loop를 시작하게 된다.

7. j loop 가 끝나면 day i에서 할 수 있는 강연 중 가장 큰 것을 선택해서 더해주면 된다. 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct info {
    int p;
    int d;
    info (int a, int b) {
        p = a; 
        d = b;
    }
    bool operator<(const info &v) const {
        return d > v.d;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cin.tie(0);

    // freopen("2109.txt", "r", stdin); 
    int n, a, b, max=0;
    cin >> n;

    vector<info> v;
    priority_queue<int> pq;
    for (int i=0; i<n; i++) {
        cin >> a >> b;
        v.push_back(info(a, b));
        if (b > max) max = b;
    }

    sort(v.begin(), v.end());
    int j=0, res=0;
    for (int i=max; i>=1; i--) {
        // 이전 j부터 시작
        for (; j<n; j++) {
            // day i 에 할 수 없는 강연
            if (v[j].d < i) break;
            pq.push(v[j].p);
        }

        // day i에 할 수 있는 강연 중 페이 큰것 선택 
        if (!pq.empty()) {
            res += pq.top();
            pq.pop();
        }
    }

    cout << res << endl;

    return 0;
}