[softeer-LV2] 금고털이(python)

문제

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

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

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

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제1

100 2
90 1
70 2

출력예제1

170

코드

import sys
input = sys.stdin.readline

w, n = map(int, input().split())

jewelry = [list(map(int,input().split())) for i in range(n)]
jewelry.sort(key=lambda x:x[1], reverse=True)

result = 0
for m,p in jewelry:
    if(w>m):
        result = result+m*p
        w = w-m
    else:
        result = result+w*p
        break

print(result)

문제이해

1. 첫 번째 줄에 배낭의 무게 w와 귀금속의 종류 n개가 주어진다.
2. 두번째 줄부터 금속의 무게 M과 금속1kg당 가격 P가 주어진다.

예제1의 출력이 170인 이유는 다음과 같다.

• 100kg까지 넣을 수 있는 가방
• 키로당 가격은 두 번째에 있는 [70, 2]가 더 크므로, 70kg 모두 담는다.
• 이때 가방엔 30kg을 더 넣을 수 있고, 현재까지 가방에 담긴 금속의 가격은 (70*2=140)이다.
• 나머지 30kg은 90kg짜리를 톱으로 썰어 담아야 한다.
• 이때 90kg 중 30kg의 가격은 (30*1=30)이다.
• 따라서 배낭에 담을 수 있는 가장 비싼 가격은 (70x2 + 30x2 = 170)이다.

풀이

sort(key=lambda x:x[1], reverse=True)를 이용했다.

금속의 무게 M과 무게당 가격 P를 받고, 가격에 따라 내림차순으로 정렬해준다.

만약 남은 배낭의 무게보다 금속의 무게가 작다면,

(남은 배낭의 무게) -= (금속의 무게)
(담은 가격) += (금속의 무게)*(금속의 키로당 가격)

만약 남은 배낭의 무게보다 금속의 무게가 크다면,

(담은 가격) += (남은 배낭의 무게)*(금속의 키로당 가격)
break //종료