[백준] 1202번 보석 도둑 C++ 코드

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
// 문제의 답이 30만 * 100만이 될 수 있으므로 long long으로 선언
ll n,k,m,v,c,res;
vector<pair<ll,ll>> jew;
vector<ll> bag;
void FASTIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}

int main() {
  FASTIO();
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> m >> v;
    jew.push_back({m,v});
  }
  while(k--) {
    cin >> c;
    bag.push_back(c);
  }
  // 무게 기준 오름차순 정렬
  sort(jew.begin(),jew.end());
  sort(bag.begin(),bag.end());
  priority_queue<ll> pq;
  int j = 0;
  for(int i = 0; i < bag.size();i++) {
  	// 가방에 들어갈 수 있는 보석 찾기
    // j의 인덱스 범위 주의
    while(j < n && bag[i] >= jew[j].first) { 
      pq.push(jew[j].second);
      j++;
    }
    // 큰 가방이면 작은 보석도 들어갈 수 있음
    if(pq.size()) {
      res += pq.top();
      pq.pop();
    }
  }
  cout << res << '\n';
  return 0;
}

답의 범위와 인덱스 범위에 주의가 필요한 문제. 정렬한 후 가방에 들어갈 수 있는 보석들을 우선순위 큐에 모아준 후, 가장 큰 값을 더해주면 된다. 참고로 C++에서 우선순위 큐는 아무 설정을 하지 않았을 때 최대힙이다.