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

난이도 : GOLD II

문제링크 : https://www.acmicpc.net/problem/1202

문제해결 아이디어

• 가방을 가벼운 순으로 정렬
• 보석을 무거운 무게 순으로 정렬 (pop()을 통해 시간복잡도를 줄이기 위해)
• 가방 무게보다 가벼운 보석중 힙을 통해 가장 값어치가 높은 보석을 담는다.
• 가방은 가벼운 순으로 정렬 했기 때문에 힙에 담겨있는 보석은 다음 가방에도 담길수가 있다.

소스코드

import sys
import heapq

input = sys.stdin.readline

jew_cnt, bag_cnt = map(int, input().split())
jew = []

for _ in range(jew_cnt):
    # 무게, 값어치
    jew.append(list(map(int,input().split())))

bag = []

for _ in range(bag_cnt):
    bag.append(int(input()))

bag.sort()
jew.sort(reverse=True)
h = []
ans = 0
for i in bag:
    while jew and i >= jew[-1][0]:
        heapq.heappush(h,-jew.pop()[1])

    if h:
       ans -= heapq.heappop(h)

print(ans)

느낀점

• 처음에 힙을 사용해야 된다는 것은 어렴풋이 짐작했지만 해결아이디어를 떠올리는데 오래걸렸다.
• 힙을 사용할때는 기존힙을 유지하면서 for문 순회가 가능한 조건을 찾아보자.