이를 위해서 귀금속의 무게와 가격을 받았을 때, 이 데이터를 귀금속의 가격이 높은 순서대로 정렬을 해주는 것으로 시작을 한다.
sorted(리스트, key=정렬 할 기준, reverse=거꾸로 돌릴 것인가의 여부)
이는 sorted 함수로 구현이 가능하다. sorted 함수를 그대로 쓰면 낮은 값 순서대로 정렬을 하기 때문에 뒤에 reverse 라는 변수를 True로 설정을 해주면 높은 순서대로 정렬이 가능하게 된다.
그리고 그 순서대로 배낭을 하나하나 채워가면 된다. 이때 배낭에 담을 수 있는 용량을 계속 확인하면서 담아줘야만 한다.
이를 코드로 작성하면 아래와 같다.
코드
import sys
# 배낭의 무게 W와 귀금속의 종류 N을 받는다.
W, M = map(int, sys.stdin.readline().split())
# 존재하는 귀금속 무게와 가격을 받을 리스트를 준비한다.
jew_list = []
# 최고 가격을 담을 변수를 준비한다.
best_price = 0
# 존재하는 귀금속 무게와 가격을 하나하나 받아 jew_list에 담는다.
for _ in range(M):
jew_list.append(list(map(int, sys.stdin.readline().split())))
# jew_list를 가격이 높은 순서대로 정렬한다.
jew_list = sorted(jew_list, key=lambda x: x[1], reverse=True)
# 각각 존재하는 귀금속의 무게와 가격을 하나하나 꺼내서
for w, p in jew_list:
# 만약에 배낭에 더이상 담을 수 없을 경우 for 루프를 끝내는 코드를 담고. (효율을 위해서)
if W==0:
break
# 해당 귀금속을 최대한 가방에 담는다. (다만 배낭에 담을 수 있는 무게는 W로 정해져 있다.)
best_price += p*min(w, W)
# 그리고 배낭에 담을 수 있는 용량을 갱신해준다.
W = max(W-w, 0)
print(best_price)
