백준 1202번: 보석 도둑(C++)

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

해당 문제를 풀 때 가장 중요한 것은 어떤 조건에서 가장 이득을 보는지 생각해야 한다. 우선 쉽게 정답을 먼저 말하면 가장 가격이 비싼 보석을 가장 무게가 적은 가방에 넣는 과정만 생각하면 상덕이가 훔칠 수 있는 보석의 최대 가격을 구할 수 있다.

우선 보석의 무게와 가격이 중복될 수 있고 가방의 무게도 중복될 수 있으므로.. 중복을 고려한 자료구조를 사용 해야 되고 보석 같은 경우 가격에 따라서 정렬 해야지 가장 비싼 보석부터 가방에 넣어볼 수 있고, 가방 같은 경우도 가장 무게가 적은 가방에 넣는 과정을 진행해야 하므로 무게에 따른 정렬이 필요하다. 따라서 다음과 같이 코드를 작성 하였다.

헷갈렸던 부분을 하나 이야기 해보자면 보석의 가격이 같을 경우 무게가 더 적은 보석을 선택해야 하는가에 대한 의문이 생길 수 있다. 이 경우에는 사실 선택하는 것이 큰 차이를 만들지 않는다. 왜냐하면 보석의 가격이 같다면 무게에 관계없이 같은 가치를 가지므로, 어떤 보석을 선택하든 결과는 같기 때문입니다.

#include <bits/stdc++.h>
#include <set>
using namespace std;

pair<int, int> jewel[300003];
multiset<int> bag;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    
    long long ans = 0;


    for (int i = 0; i < n; i++)
    {
        cin >> jewel[i].second >> jewel[i].first;
    }

    sort(jewel, jewel + n);

    for (int j = 0; j < k; j++)
    {
        int c;
        cin >> c;
        bag.insert(c);
    }
      
    for (int i = n - 1; i >= 0; i--)
    {
       auto it = bag.lower_bound(jewel[i].second);
       if (it == bag.end()) continue;
       
       ans += jewel[i].first;
       bag.erase(it);

    }
        
    cout << ans << '\n';
}

아래는 바킹독님 해설이다.

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/ac7c8dedea8b446b9f85563064ed3a6f
#include 
using namespace std;

#define X first
#define Y second

int n, k;
pair<int, int=""> jewel[300003]; // {가격, 무게}
multiset bag;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;

  // 정렬의 편의를 위해 무게/가격을 반대로 입력받음
  for(int i = 0; i < n; i++)
    cin >> jewel[i].Y >> jewel[i].X;
  sort(jewel, jewel+n);

  for(int i = 0; i < k; i++){
    int c;
    cin >> c;
    bag.insert(c);
  }

  long long ans = 0;

  for(int i = n-1; i >= 0; i--){
    int m, v;
    tie(v, m) = jewel[i];
    auto it = bag.lower_bound(m);
    if(it == bag.end()) continue;
    ans += v;
    bag.erase(it);
  }
  cout << ans;
}</int,>