[소프티어][그리디] 금고 털이

금고 털이

Softeer - 현대자동차그룹 SW인재확보플랫폼

• 내 풀이
  • knapsack 문제인줄 알았으나 잘라서 넣을 수 있음 => 그리디

import sys
import heapq
input=sys.stdin.readline


w,n=map(int,input().split())
jewlery=[]
answer=0
for _ in range(n):
    m,p=map(int,input().split())
    heapq.heappush(jewlery, (-p,m))

while w>0:
    price,weight=heapq.heappop(jewlery)
    tmp=min(weight,w)
    answer+=tmp*(-price)
    w-=tmp

    if w==0:
        break

print(answer)