[PS스터디 심화반] 2주차 백준 보석도둑

개요

 

적지 않은 사람들이 갈려나간 문제입니다. 저번 문제에서도 나온 이야기지만 문제를 해석하고 제대로 이해하는 것이

PS를 함에 있어서 정말 중요한 것이라는 것을 다시 한 번 느낄 수 있었습니다.

 

 

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

1202번: 보석 도둑

 

 

 

리뷰와 피드백

 

 

이번 문제는 문제의 특성 상 그리디적인 접근과 우선순위 큐를 활용하는 문제였습니다. 주어진 시간을 고려하였을 떄

거의 이 방식을 의도하고 낸 문제가 아닌가 생각 들었습니다.

 

처음에는 Parametric search를 요하는 문제가 아닌가 생각을 하였는데, 비교 조건이 하나 이상이며

꾸준히 증감하는 기울기의 그래프를 구할 수 없어 끝내 아님을 깨달았습니다. 

우선순위 큐를 이용하는 문제는 아직 경험해 본 적이 많이 없어 애 먹었네요.

 

 

 

 

 

코드 전문

 

 

 

 

#include <iostream>   // 상대적으로 큰 가방은 상대적으로 작은 가방이
#include <vector>     // 수용할 수 있는 크기를 포함하는 관계로
#include <algorithm>  // 작은 가방부터 자신이 수용할 수 있는 최고가의 보석을
#include <queue>      // 먼저 넣어나가면 최대값을 얻을 수 있다는 가정.

#define WEIGHT first
#define PRICE second

using namespace std;

using info = pair<int, int>;

priority_queue<int> pq;
int n, k; 

int main() {
  cin >> n >> k;
  vector<info> jewel_info(n); 
  for (int i = 0; i < n; ++i) cin >> jewel_info[i].WEIGHT >> jewel_info[i].PRICE;
  vector<int> bag_info(k);
  for (int i = 0; i < k; ++i) cin >> bag_info[i];  

  sort(jewel_info.begin(), jewel_info.end());
  sort(bag_info.begin(), bag_info.end());

  unsigned long long ans = 0;
  
  // 큰 가방은 작은 가방의 범위를 포함하니 이전 Maxheap(pq)을 이어 사용할 수 있다.
  for (int i = 0, pq_idx = 0; i < k; ++i) { 
    // 현재 가방이 수용할 수 있는 모든 보석을 Maxheap(pq)에 추가
    while (pq_idx < n && jewel_info[pq_idx].WEIGHT <= bag_info[i])
      pq.push(jewel_info[pq_idx++].PRICE);
      
    // Maxheap에 하나라도 보석이 존재한다면, 현재 가방에 넣는다.
    if (!pq.empty()) {
      ans += pq.top();
      pq.pop();
    }
  }

  cout << ans;
}

 

 

 

 

향후 방침, 느낀 점

 

 

 

우선순위 큐를 제대로 사용할 수 있었던 좋은 기회였단 생각이 들었습니다. 재밌네요.

그치만 분합니다!!!!!!!!!!!!!!!!!!!!