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

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395

Softeer

 

[난이도] level2
[유형] 정렬

[풀이]
무게당 가격이 높은것부터 배낭에 넣으면 됩니다.
pair 배열에 {무게당 가격(Pi),금속의 무게(Mi)} 로 저장한 뒤 정렬하면
무게당 가격의 내림차순으로 정렬이 됩니다.
N-1번 금속부터 거꾸로 금속을 넣을 수 있을만큼 넣어으면서 금속의 가격을 계산해서 더해주면 됩니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,W,ans;
pair<int,int> v[1000000];
int main(){
    scanf("%d%d",&W,&N);
    for(int i=0;i<N;i++){
        int m,p;
        scanf("%d%d",&m,&p);
        v[i]={p,m};
    }
    sort(v,v+N);
    for(int i=N-1;i>=0,W>0;i--){
        int k = min(v[i].second,W);
        W-=k;
        ans+=k*v[i].first;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/금고털이.cpp