[백준 1202번 파이썬] 보석 도둑

백준 1202번 링크)

---

---

해결)

heapq를 사용해서 최대,최소힙을 사용하였다.
가방의 사이즈가 작은 것부터, 넣을 수 있는 보석 중 가장 가치가 큰 보석을 넣어주었다.
보석은 heapq.heappush로 무게가 작은 것 부터 넣어주었다.
가방은 순서대로 넣고 sort로 오름차순 해주었다.

현재 보석은 오름차순으로 되어있으므로

• 첫번째 보석의 무게보다 가방무게가 크면 -> list에 heappush로 큰 순서로 넣어준다.
  (이 때 heapq는 최소힙만 지원하므로 값 앞에 -를 붙이면 최대힙처럼 사용가능)
• heappop으로 list에서 가장 큰 값을 뺀 후 결과값에 더해준다.
  (이 때 다시 값 앞에 -를 붙여야 함)

---

import sys
import heapq
input=sys.stdin.readline

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

jewel=[]
for _ in range(n):
    m, v = map(int, input().split())
    heapq.heappush(jewel, (m, v))
    
bag=[]
for _ in range(k):
    bag.append(int(input())
bag.sort()

list=[]
res=0

for i in bag:
    while len(jewel)!=0 and i >=jewel[0][0]:
        heapq.heappush(list, -heapq.heappop(jewel)[1])
    if len(list)!=0:
        res-=heapq.heappop(list)
    elif len(jewel)==0:
        break
print(res)