[ 1202 ] [ heap ] 보석 도둑

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

1202번: 보석 도둑

---

풀이 과정

---

1. 그냥 진행하면 가방도 최대 30만개고, 보석도 최대 30만개이므로 시간초과가 나타나므로 최대 히프로 풀이한다.
2. 우선 보석을 무게 순으로 최소 히프에 넣어주고, 가방은 오름차순으로 정렬시켜 준다.
3. 가장 가벼운 가방에서부터 순차적으로 루프를 돈다.
   1. 현재 가방에 넣을 수 있는 보석들을 최소 히프에서 하나씩 꺼내면서 보석의 가격 순으로 최대 히프에 넣어준다.
   2. 넣어주는 작업이 끝나면, 최대 히프에서 값을 하나 꺼내서 더해준다. 가벼운 가방에서 무거운 가방 순서로 진행하므로 다음 가방에는 무조건 넣을 수 있는 보석이기 때문에 무게는 같이 저장할 필요가 없음. 최대 히프에서 꺼낸 값이 현재 가방에 넣어줄 보석의 가격이다.
4. 보석 가격의 합을 출력시켜 준다.

---

소스 코드

---

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
jewel = []

for _ in range(N):
    M, V = map(int, input().split())
    heapq.heappush(jewel, [M, V])

backpack = [int(input()) for _ in range(K)]
backpack.sort()

jewel_value_heap = []
answer = 0
for b in backpack:
    # 현재 가방에서 가능한 보석 값들 최대 히프에 넣어줌
    while jewel and jewel[0][0] <= b:
        heapq.heappush(jewel_value_heap, -heapq.heappop(jewel)[1])

    # 최대 히프에서 값 하나 꺼내서 더해줌(현재 가방에 들어갈 보석)
    if jewel_value_heap:
        answer -= (heapq.heappop(jewel_value_heap))

print(answer)