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

• 백준 링크: 1202번: 보석 도둑
• solved.ac 난이도: 골드 II
• 시간 제한: 1 초
• 메모리 제한: 256 MB

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

코드

import sys, heapq

N, K = map(int, sys.stdin.readline().split())
jew = []
for _ in range(N):
    heapq.heappush(jew, list(map(int, sys.stdin.readline().split())))
bags = []
for _ in range(K):
    bags.append(int(sys.stdin.readline()))
bags.sort()

answer = 0
tmp_jew = []
for bag in bags:
    while jew and bag >= jew[0][0]:
        heapq.heappush(tmp_jew, -heapq.heappop(jew)[1])
    if tmp_jew:
        answer -= heapq.heappop(tmp_jew)
    elif not jew:
        break
print(answer)