[cpp]금고털이

---

문제 난이도

> ★★☆☆☆

---

 

문제 유형

> greedy

 

greedy algorithm 대표 문제 : 백팩

 

---

 

풀이 과정

pair<int, int> 함수를 사용하여

first: M_i(금속 무게)

second: P_i(무게당 가격)을 넣어주고

 

무게당 가격에 대해 내림차순 정렬 후 한 번의 루프로 배낭의 무게가 0보다 작을 때까지

금속 무게에 대한 가격을 result 변수에 더해주었습니다.

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

bool compare_func(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    else
        return a.second > b.second;
}

int main()
{
    int W, N;
    int metal, price;
    int result=0;
    vector<pair<int, int> > metal_price;

    cin >> W >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> metal >> price;
        metal_price.push_back(make_pair(metal, price));
    }
    
    sort(metal_price.begin(), metal_price.end(), compare_func);
    
    for(int i = 0; i < metal_price.size(); i++)
    {
        if (W <= 0)
            break;

        if(W - metal_price[i].first >= 0)
        {
            result += metal_price[i].first * metal_price[i].second;
            W -= metal_price[i].first;
        }
        else
        {
            result += metal_price[i].second * W;
            W = 0;
        }
    }
    cout << result;
}