Solution (오답)

• d를 기준으로 정렬 한 후에, for문으로 순회하며 각 날에 들어갈 수 있는 값 중에 가장 큰 값을 골랐다. 이때의 문제점은

3
1 1
10 2
10 2

와 같은 테스트 케이스에서 2일, 3일에도 강연을 갈 수 있는 경우를 제대로 체크하지 못한 것이었다.

Solution (정답)

• 배열을 d를 기준으로 정렬한 후에, 배열을 순회하면서, priority_queue에 강연료(p)를 넣는다. 이때, 만약 priority_queue의 크기(size)가 현재 index의 d보다 크다면 priority_queue에서 한 값을 뺀다. 이를 위해 pq는 오름차순으로 선언하였다.

순회강연

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <string>
#include <stack>
#include <list>
#include <unordered_set>
#include <sstream>
#include <deque>
#include <math.h>
#include <map>
#include <set>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int,int>> vec;
int n;

void Solution()
{
    sort(vec.begin(),vec.end());
    int sum = 0;
    for(int i  =0  ; i<vec.size(); i++){
       pq.push(vec[i].second);
       sum += vec[i].second;
       if(vec[i].first < pq.size()){
        int top = pq.top();
        sum -= top;
        pq.pop();
       }
    }
    cout << sum << '\n';
    
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solution();
}