배우기를 멈추는 사람은 20세건 80세건 늙은 것이다.

[Greedy] jewelryThief - priority_queue(heap)

예제: https://www.acmicpc.net/problem/1202

// 보석상 도둑 그리디 알고리즘
// 보석수, 가방수
// 한개의 가방에는 한개의 보석만 넣을 수 있다.
// 보석 무게, 보석 값어치
// 가방들마다 넣을 수 있는 무게

// algorithm > sort
// vector, queue
// pair, priority_queue(heap)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define SIZE 300000

int main() {
   int jewelryCount, bagCount;
   cin >> jewelryCount >> bagCount;

   // ---------------------------- //

   vector<pair<int, int>> jewelry;
   double weight, value;
   for(int i=0; i<jewelryCount; i++) {
      cin >> weight >> value;
      jewelry.push_back({ weight, value });
   }

   // ---------------------------- //

   int bagWeight[SIZE];
   for(int i=0; i<bagCount; i++) {
      cin >> bagWeight[i];
   }
   sort(bagWeight, bagWeight+bagCount);
   sort(jewelry.begin(), jewelry.end());

   // ---------------------------- //

   priority_queue<int> heap;
   long long maxValue = 0;
   for(int i=0, j=0; i<bagCount; i++) {
      // 가방에 넣을 수 있는 보석들을 모두 힙에 넣는다.
      while(j < jewelryCount && jewelry[j].first <= bagWeight[i]) {
         heap.push(jewelry[j].second);
         j++;
      }
      // 힙에 넣은 것들중 크기가 제일 큰 것을 지금 가방에 넣는다.
      if(heap.size()) {
         maxValue += heap.top();
         heap.pop();
      }
   }

   cout << maxValue << endl;

   return 0;
}