[알고리즘] 백준 2109 순회강연 // 그리디 , pq, 최대값은 최소를 적게 or 최대를 많게

https://www.acmicpc.net/problem/2109

* 풀이1

• day기준 오름차해서 각각 day에서 비싼거 뽑으면 될듯?

• 참고) pq에 줄 cmp는 struct로 줘야함

struct cmp {
    bool operator()(const pair<int,int>& p1, const pair<int,int>& p2) {
        return p1.first < p2.first; 
    }
};

 

* 풀이2

• day기준 오름차, 내림차 -> 오름차 선택
• 최대 = 최소를 적게 or 최대를 많게 -> 최소를 적게 선택
• pq.size에 day의미 부여
• greater(최소힙) => 돈 적은거 pop

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

int n,ret;
vector<pair<int,int>> v;
priority_queue<int, vector<int>,greater<>> pq; //최소힙

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

   cin>>n;
   for(int i=0;i<n;++i) {
      int p,d;
      cin>>p>>d;
      v.push_back({d,p}); // { 일, 돈 }
   }
   sort(v.begin(),v.end()); // 일기준 오름차

   for(int i=0;i<n;++i) {
      pq.push(v[i].second); // 돈 추가

      //일수가 여러개인경우, 적은돈 제거
      if(pq.size() > v[i].first) { 
         pq.pop();
      }
   }

   while(pq.size()) {
      ret+=pq.top(); pq.pop();
   }
   
   cout<<ret;
   

   return 0;
}