[Softeer]금고털이 파이썬 풀이

금고털이¶

문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395
해결방안: greedy

1. 무게당 가격 P가 가장 높은 금속을 담는다.
   
2. 배낭의 무게를 고려한다.
   
3. 다음으로 무게당 가격 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