[C++] softeer Level2 금고털이

Table of Contents

• 문제
• 계획
• 풀이

문제

• softeer Level2 금고털이

최대 무게가 정해진 가방과 무게 및 무게 당 가격이 정해진 보석들이 있다. 최대한 비싸게 보석을 털어가고 싶다. 보석은 자를 수 있다.

계획

처음엔 knapsack인 줄 알았는데 다시 보니 그리디인 것 같다. 비싼 것부터 최대한 담고, 남은 자리에 그 다음으로 비싼 걸 담으면 되지 않을까? 이건 예제 보면서 다시 생각해봐야 할 것 같다.

편의상 내가 알아보기 쉬운 단위를 붙였으나 원래 문제에는 단위가 없다.

가방 총 무게는 100이고 보석은 2종류 있다. 하나는 1원/g인 보석 90g, 다른 하나는 2원/g인 보석 70g.
먼저 비싼 보석은 두 번째 보석이니 그걸 최대한 담아본다. 가방에는 70g이 채워졌고 가치는 140원.
그 다음 남은 30g 만큼을 1원짜리 보석을 잘라 담는다. 무게는 100g 채웠고 가치는 140 + 30 = 170원.

knapsack과의 차이는 무게 조절이 가능하다는 것. 그것 때문에 뭔가 그리디로 안 되는 반례를 생각하려고 해도 생각이 안 난다. 일단 써보기로.

알고리즘 구상은 정렬 후 잘라 담기. 우선순위 큐 쓰면 되겠네.

풀이

괜히 knapsack 아닌가 하고 헷갈려서 문제 이해가 좀 걸리긴 했지만 내 구상이 맞아서 바로 통과했다.

C++의 우선순위 큐는 기본적으로 내림차순 정렬을 하고, 내용물을 pair로 넣어도 똑같이 내림차순 정렬을 해주기 때문에 보석의 가격과 무게를 pair로 묶어서 저장하면 (1) 비싸고 (2) 양 많은 보석부터 나오게 된다. 입력과 동시에 정렬이 되는 셈이니 가방에 담을 때는 우선순위 큐에서 나오는 것부터 담으면 되고, 가방에 공간이 부족하면 보석을 자르면 된다. 근데 보석은 크기도 중요해서 자르면 절대 같은 가격 못받을 텐데

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

/*
 * https://softeer.ai/practice/info.do?idx=1&eid=395
 */

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  int bag, n, jewel, price;
  int bag_total = 0, price_total = 0;
  priority_queue<pair<int, int>> jewel_box;
  pair<int, int> buffer;

  cin >> bag >> n;

  for (int i = 0; i < n; i++) {
    cin >> jewel >> price;
    jewel_box.emplace(price, jewel);
  }

  while (bag_total < bag && !jewel_box.empty()) {
    buffer = jewel_box.top();
    jewel_box.pop();
    jewel = buffer.second;
    price = buffer.first;

    if (jewel > bag - bag_total)
      jewel = bag - bag_total;

    bag_total += jewel;
    price_total += jewel * price;
  }

  cout << price_total << "\n";

  return 0;
}