소스 코드

/*
제출 일시
2023-11-01 20:40:51
채점 결과 : 맞았습니다
득점     : 100.0/100.0
실행 시간 : 174 ms
메모리   : 9.08 MB
*/
#include<iostream>
#include <vector>
#include <queue>
#define endl "\n"

using namespace std;

typedef pair<int, int> gem;

int w; // 배낭 무게
int n; // 귀금속 종류
int price; // 현재 배낭의 가치
priority_queue<gem, vector<gem>> pq; // 무게당 가격이 비싼 순으로 정렬되는 우선순위 큐: {무게당 가격, 무게}

void input()
{
  cin >> w >> n;
  priority_queue<gem, vector<gem>>().swap(pq); // pq size 0으로 초기화

  for (int i = 0; i < n; ++i) 
  {
    int kg, pricePerKg;
    cin >> kg >> pricePerKg;
    pq.emplace(pricePerKg, kg);
  }

  price = 0;
}

void solve() 
{
  while (w > 0)
    {
      gem curGem = pq.top(); pq.pop();
      if (w >= curGem.second) 
      {
        w -= curGem.second;
        price += curGem.first * curGem.second;
      }
      else 
      {
        price += curGem.first * w;
        w = 0;
      }
    }

  cout << price << endl;
}

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  input();

  solve();
  
  return 0;
}

해설

1. 무게당 가격이 비싼 보석부터 꺼내서 쓰기
   : 이를 위해 우선순위 큐로 정렬
2. 남은 배낭무게가 0이 될때까지 아래 과정 반복
3. 남은 배낭무게가 우선순위 큐에서 꺼낸 보석의 무게보다 같거나 큰 경우
   : 남은 배낭무게 업데이트 및 현재 가격 업데이트
4. 남은 배낭무게가 우선순위 큐에서 꺼낸 보석의 무게보다 작은 경우
   : 현재 가격 업데이트 이후 남은 배낭무게 0으로 만들어주기