[Softeer level2] Python 금고털이

Softeer

Softeer

문제

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

 

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

 

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

 

문제풀이

입력이 [90,1] [70,2] 이런식으로 들어오면 귀금속의 가격을 기준으로 정렬을 한뒤 가방의 무게를 빼주면서 계산하면 되는 문제이다.

import sys
input = sys.stdin.readline
W, N = map(int, input().split())

j = [list(map(int, input().split())) for _ in range(N)]
j.sort(key=lambda x:x[1], reverse=True)
answer = 0
for weight, price in j:
    if(W > weight):
        answer += weight * price
        W -= weight
    else:
        answer += W * price
        break

    
print(answer)