[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