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

문제

2109번: 순회강연

풀이

그리디, 우선순위 큐

 

강연료를 최대로 받기 위해서는, 강연료가 크면서 기간이 많이 남은 강연은 최대한 나중에 하고, 기간이 짧은 강연을 빠른 날짜에 해야 한다. 

우선순위 큐를 이용해서, 강연료가 크면서 남은 기간이 오래 남은 강연 순서로 탐색한다. 현재 탐색 중인 강연을 최대한 나중으로 미뤄서 실행하면 기간이 얼마 남지 않으면서 강연료가 큰 강연을 앞에 날짜에 실행할 수 있다. 

// 강연료가 크면서, 남은 기간이 오래 남은 순서로 탐색한다. 
int answer = 0;
while (!pq.empty())
{
    pair<int, int> current = pq.top();
    pq.pop();

    // 현재 강연을 최대한 나중으로 미뤄야 기간이 짧으면서 강연료가 큰 강연을 실행할 수 있다. 
    for (int i = current.second; i > 0; --i)
    {
        if (days[i] == false)
        {
            days[i] = true;
            answer += current.first;
            break;
        }
    }
}

코드

#include <iostream>
#include <queue>

using namespace std;

bool days[10001];
priority_queue<pair<int, int>> pq;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

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

        pq.push(make_pair(p, d));
    }

    // 강연료가 크면서, 남은 기간이 오래 남은 순서로 탐색한다. 
    int answer = 0;
    while (!pq.empty())
    {
        pair<int, int> current = pq.top();
        pq.pop();

        // 현재 강연을 최대한 나중으로 미뤄야 기간이 짧으면서 강연료가 큰 강연을 실행할 수 있다. 
        for (int i = current.second; i > 0; --i)
        {
            if (days[i] == false)
            {
                days[i] = true;
                answer += current.first;
                break;
            }
        }
    }

    cout << answer;

    return 0;
}