[소프티어] 금고털이 (C++)

👓 문제 설명

---

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

---

💣 제한 사항

• 1 ≤ N ≤ 106인 정수
• 1 ≤ W ≤ 104인 정수
• 1 ≤ Mi, Pi ≤ 104인 정수

---

🚨 접근 방법

얼핏보면 DP 문제로 착각할 수 있다.
하지만 단순 정렬 문제이다.
Why? : 문제 설명 맨 마지막을 보면 톱으로 자른 무게만큼의 가치를 가져갈 수 있다고 하였다.
처음에 Knapsack 문제인 줄 알았지만 이 문장을 보고 다시 풀었다.
vector<pair<int,int>>를 만들고 이 안에 각 보석의 무게와 무게 당 가치를 저장한다.
cmp 함수를 만들어 .second를 내림차순으로 정렬한다.
벡터의 맨 앞에서부터 담을 수 있을만큼 담는다.

---

🚈 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(pair<int,int>a,pair<int,int>b){
  return a.second>b.second;
}

int main(int argc, char** argv)
{
  int answer=0,cur_weight=0;
  vector<pair<int,int>>bag;
  int w,n,m,p;
  cin>>w>>n;
  // 배낭 무게, 금속 종류, 각 금속 별 보유 무게와 무게 1당 가격 입력
  for(int i=0;i<n;i++){
    cin>>m>>p;
    bag.push_back(make_pair(m,p));
  }
  // 결국 비싼 금속을 최대한 담고 남은 공간은 그 다음으로 비싼 금속을 담을 수 있을 때 까지 자르면 된다.
  // 입력 예시 1 -> 무게 당 2원 금속을 70만큼 담은 후 무게 당 1원 금속을 30만큼 담으면 총 140+30 = 170의 가격을 담을 수 있다.
  
  // 금속의 값 어치 순으로 정렬하기
  sort(bag.begin(),bag.end(),cmp);

  // bag의 앞에서 부터 담을 수 있을만큼 담기
 
  for(auto p:bag){
   while(cur_weight<w){
    if(p.first!=0){
        cur_weight++;
        p.first--;
        answer+=p.second;
      }
     else{
       break;
     }
    }
  }
  cout<<answer;
   return 0;
}