[Softeer]금고털이 파이썬 풀이
금고털이¶
문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395
해결방안: greedy
- 무게당 가격 P가 가장 높은 금속을 담는다.
- 배낭의 무게를 고려한다.
- 다음으로 무게당 가격 P가 높은 금속을 담는다
input data
무게당 가격 P를 정렬해야 하므로 이에 적합한 자료형에 담는다.
이 때, 금속의 무게 M을 고려해야 하므로 튜플형으로 묶어주면 연산하기에 편리하다.
tuple형의 자료를 자동으로 정렬해주는 자료구조 -> heap
In [15]:
import heapq
W, N = [int(x) for x in input().split()]
products = []
for _ in range(N):
M, P = [int(x) for x in input().split()]
heapq.heappush((products), (-P, M))
total = 0
while products:
P, M = heapq.heappop(products)
P = -P
if M >= W:
print(total + (W*P))
break
total += M*P
W -= M
if W<=0:
print(total)
break
100 2 90 1 70 2 170