1202번 보석 도둑

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

---

아이디어

주어진 가방에 해당하는 보석들을 최대힙에 넣어 더하는 문제이다.

1) 보석, 가방 모두 오름차순 정렬
2) 가방 무게 작은 것부터 넣을 수 있는 보석들 최대 힙에 가격만 넣기
3) 다 넣었으면 가장 큰 0번째 원소만 결과값에 추가

---

코드

import sys
import heapq
input = sys.stdin.readline

n,k = map(int, input().split()) # 보석 개수, 가방 개수
diamonds = [list(map(int, input().split())) for _ in range(n)] # [무게, 가격]
bags = [int(input()) for _ in range(k)] # 가방 최대 무게

diamonds.sort(key=lambda x: x[0]) # 무게 오름차순
bags.sort()
answer = 0
heap = [] # 보석의 가격 저장 힙

for bag in bags:
    while diamonds and diamonds[0][0] <= bag: # 보석이 존재하고 가방 무게보다 작거나 같으면
        heapq.heappush(heap, -diamonds[0][1]) # 가격을 최대힙에 넣기(-붙임)
        heapq.heappop(diamonds) # 넣은 보석은 보석리스트에서 빼기
    if heap: # 존재하면
        answer -= heapq.heappop(heap) # 가격이 가장 높은 보석을 더하기(처음에 음수로 넣었으므로 -)
print(answer)