[소프티어] 금고털이 / C++ 해설 / Python 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

 

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

공식 해설: https://softeer.ai/class/algotutor/detail.do?id=66 

Softeer

 

코드(C++)

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

using namespace std;
typedef pair<int, int> P;
int main(int argc, char** argv)
{
	int w, n;
	int res = 0;
	vector<P> v;
	cin >> w >> n;
	for(int i = 0 ; i < n ; i ++){
		int w, v_per_kg;
		cin >> w >> v_per_kg;
		v.push_back({-v_per_kg, w});
	}
	sort(v.begin(), v.end());

	for(auto &x : v){
		if(w == 0) break;
		res += (min(w, x.second)) * (-x.first);
		w -= min(w, x.second);
	}
	
	cout << res;
	return 0;
}

코드(Python)

import sys
input=sys.stdin.readline

Weight, N=map(int,input().split())

Bank=[]
for n in range(N):
    a,b=map(int, input().split())
    Bank.append((b,a))
    


Bank.sort(key=lambda x: x[0], reverse=True)


Bank.sort(reverse=True)
result=0
for B in Bank:
    if Weight==0:
        break
    if Weight>=B[1]:
        result+=B[0]*B[1]
        Weight-=B[1]
        continue
    else:
        result+=B[0]*Weight
        break
print(result)

 

해설

 

1kg 당 가치가 가장 높은 보석부터 무게제한 W가 안넘을때까지 안에 넣는다.

 

1kg 당 가치를 기준으로 내림차순으로 정렬을 수행한 뒤 1kg 당 가치가 높은 순서부터 W가 안넘을때까지 쌓아넣는다.