python 백준 1202 보석 도둑

• https://www.acmicpc.net/problem/1202

로직

• 보석을 무게순으로 정렬
• 가방을 무게 한도순으로 정렬
• 무게한도가 가장 낮은 가방부터 채우는 형식
• 현재 가방에 담을 수 있는 보석이면 can_theft에 heapq를 이용하여 추가(최대 값어치를 가진 보석이 pop되게 하기 위해)
• 현재 가방에 담을 수 있다면 다음 가방은 무게 한도가 더 크므로 다음 가방에도 담을수 있음 => can_theft를 유지
• 현재 가방에 담을 수 있는 보석이 모두 can_theft에 담기면 그 중 가장 큰 값어치를 가진 보석을 담음

import sys
from heapq import heappush,heappop
N,K = map(int,sys.stdin.readline().split())
jewel = []

for _ in range(N):
    M,V = map(int,sys.stdin.readline().split())
    jewel.append((M,V))
jewel.sort(reverse=True)
backpack = [int(sys.stdin.readline()) for _ in range(K)]
backpack.sort()
ans = 0

can_theft = []
# 무게순으로 가방에 보석을 넣음
for bag in backpack:
    while jewel and bag >= jewel[-1][0]:
        # 무게상 훔칠수 있으면 can_theft에 넣음, value 순서로
        heappush(can_theft,-jewel.pop()[1])
    # 해당 가방에 넣을 것중 가장 값비싼거 추가
    if can_theft:
        ans -= heappop(can_theft)
    # 넣을 보석도 없고 더이상 남은 보석이 없음
    elif not jewel:
        break
print(ans)