[C++] 백준 1781번 컵라면

문제

백준 1781번 컵라면

풀이

데드라인과 컵라면 수를 pair로 묶은 후 데드라인을 기준으로 정렬한다.
데드라인이 적은 문제부터 풀며 해결시의 컵라면을 minheap에 저장한다. heap의 크기가 n이라면 n개의 문제를 해결했다는 것이고 한 문제당 1의 시간이 소요되므로 더이상 데드라인이 n이하인 문제를 풀 수 없다는 뜻이다. 이때 n이하인 문제와 만나면 현재까지 푼 문제중 컵라면을 가장 적게 주는 문제와 비교해 더 큰쪽을 선택한다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#define endl '\n'

using namespace std;

int n;
vector<pair<int,int>> v;
priority_queue<int, vector<int>, greater<int>> minheap;

int solve(){
  for (auto p : v){
    if (minheap.size() == p.first){
      if (minheap.top() < p.second){
        minheap.pop();
        minheap.push(p.second);
      }
    }
    else {
      minheap.push(p.second);
    }
  }
  int ans = 0;
  while (!minheap.empty()){
    ans += minheap.top();
    minheap.pop();
  }

  return ans;
}

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

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;
  v.resize(n);

  for (int i=0; i<n; i++){
    int a,b;
    cin >> a >> b;

    v[i] = {a,b};
  }

  sort(v.begin(), v.end());

  cout << solve();
}