baekjoon 1202:보석 도둑

baekjoon 1202 보석 도둑

1202번 보석 도둑

접근

크기가 너무 크기 때문에 dp는 절대 아니라고 생각했다.
생각해보니 크기가 작은 가방부터 채우되, 각 가방에 들어가는 보석중 최대 가격을 채우면 될 것 이라고 생각했다.
이를 구현하기 위해 vector로 for문을 계속 돌리면 O(n^2)의 시간복잡도를 가지게 된다고 생각했다.
그런데 이를 priority_queue를 이용하면 삽입, 추출에 모두 O(logn)의 시간 복잡도를 가지므로.
전체 총 O(nlogn)에 문제를 풀 수 있었다.

코드

//1202
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, k; cin >> n >> k;
  vector<pair<int, int>> gem(n);
  vector<int> backpack(k); 
  for(int i = 0; i < n; i++){
    int m, v;
    cin >> m >> v;
    gem[i] = {m, v};
  }
  for(int i = 0; i < k; i++){
    cin >> backpack[i];
  }
  sort(gem.begin(), gem.end()); //{m, v}
  sort(backpack.begin(), backpack.end());
  priority_queue<pair<int, int>> pq; //{v, m}
  long long int ans = 0;
  int backpackIndex = 0;
  for(int i = 0; i < n; i++){
    if(i == n-1){
      bool isLastPushed = false;
      while(backpackIndex < k){
        if(gem[i].first <= backpack[backpackIndex] && !isLastPushed){
          pq.push({gem[i].second, gem[i].first});
          ans+=(long long int)pq.top().first;
          pq.pop();
          isLastPushed = true;
        }
        else{
          if(!pq.empty()){
            ans+=(long long int)pq.top().first;
            pq.pop();
          }
        }
        backpackIndex++;
      }
      break;
    }
    while(backpackIndex < k){
      if(gem[i].first > backpack[backpackIndex]){
        if(!pq.empty()){
          ans += (long long int)pq.top().first;
          pq.pop();
        }
        backpackIndex++;
      }
      else{
        pq.push({gem[i].second, gem[i].first});
        break;
      }
    }
  }
  cout << ans;
  


  return 0;
}

배운 점

시간복잡도를 고려하면서 코드를 생각하는 방법이 뭔지 좀 알 것 같다.