[알고리즘] 백준 1787 컵라면 // 그리디 , pq

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

 

* 풀이

• 최대값은 최대를 많게 하거나, 최소를 적게하거나!
• 그리디는 정렬, pq
• day 순정렬 => 배치를 신경안써도됨

• 최소힙 => 이전날짜가 비효율적인경우, 그걸 뺄수있음
  • day: 1  2     2 
  • 컵 :   1 100 200
  • day1은 선택안하는게 나았음!

 

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

int n, ret; // 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 a, b;
      cin >> a >> b; // a: 데드라인, b: 컵라면 개수
      v.push_back({a, b}); // 벡터에 저장
   }

   // 데드라인을 기준으로 오름차순 정렬
   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;
}