백준 2109번 순회강연 ( C++ )

문제

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

 

해설

그리디 알고리즘을 사용하면 되는 문제

d가 2인 대학의 경우 1에도 갈 수 있다는 점을 생각해서 풀어야 함

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
int n, d, p, ret;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    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;
}