Implement 소프티어 금고 털이 Level2

https://softeer.ai/app/assessment/index.html?xid=41187&xsrfToken=GqOGAPTHxdW4H9tiPzQNWSohI14FqXlw&testType=practice

Candidate | Softeer Assessment UI

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

 

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

 

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

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

 

문제 해결

주어진 조건에서 전동톱을 가지고 톱으로 자를 수 있다라는 것을 보고 그리디 문제라는것을 파악했다. 무게가 많이 나가더라도 자를 수 있다면, 무조건 가장 가치가 높은 귀금속부터 넣는게 이득이다. 따라서 귀금속 중 가장 가치가 높은 귀금속을 기준으로 정렬한 뒤 무게에 맞게 가방에 넣어주면 되는 아주 기본적이고 쉬운 난이도의 문제이다!

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

typedef struct weihgt_price{
  ll price;
  ll weight;
}wp;

// 배낭의 무게 W, 귀금속의 종류 

bool com(wp wp1, wp wp2){
  return wp1.price < wp2.price;
}
int main(int argc, char** argv)
{
  // 배당의 무게 100, 귀금속의 종류 2
  // 1번 귀금속의 무게 90,  가격 1
  // 2번 귀금속의 무게 70, 가격 2

  // 가장 가격이 높은 거를 가져가야함

  ll weight = 0; ll N = 0; ll answer = 0;
  cin >> weight >> N ;

  vector<wp>w_p;

  wp temp;
  for(ll i=0; i<N; i++){
    cin >> temp.weight >> temp.price;
    w_p.push_back(temp);
  }

  sort(w_p.rbegin(), w_p.rend(), com);

  for(ll i=0; i<N; i++){
    if(weight >= w_p[i].weight){
      answer += w_p[i].weight * w_p[i].price;
      weight -= w_p[i].weight;
    }
    else{
      answer += weight * w_p[i].price;
      break;
    }
  }
  cout << answer << "\n";

   return 0;
}