[백준] 1202 "보석 도둑" -python

 

알고리즘

 가방 무게를 오름차순으로 정렬하면서 차례대로 순회하고 이때 가방 무게보다 작은 w를 가진 보석을 모두 최대힙에 넣어둔 뒤 각 차례마다 최대힙에서 pop연산을 수행하면 그리디하게 각 단계에서의 최선의 경우를 뽑을 수 있다. 핵심은 힙에 들어가 있는 보석들은 다음 순회때도 무조건 포함될 수 있기 때문에 수행 가능한 알고리즘이다.

 

소스코드

# 보석 도둑
import heapq
import sys

n, k = map(int, sys.stdin.readline().split())

items = []
for _ in range(n):
    w, v = map(int, sys.stdin.readline().split())
    items.append([w, v])

bags = []
for _ in range(k):
    bags.append(int(sys.stdin.readline()))

items.sort(reverse=True)
bags.sort()

result = 0
c = []
for bag in bags:
    while items and items[-1][0] <= bag:
        heapq.heappush(c, -items.pop()[1])
    if c:
        result += -heapq.heappop(c)
        
print(result)

느낀점

 처음에 최대가치 순으로 가방을 정렬하여 2중 for문을 돌았지만 시간초과가 나왔다. 그래서 질문게시판에 가서 힙을 활용하라는 힌트를 얻었지만 잘 이용하지 못해서 계속 시간초과가 나왔다. 참다가 구글링을 하였고 한 고수분의 아이디어를 이해하고 코드를 구현하였다. 힙을 저렇게 활용할 수 있음에 신기했고 나도 여러 문제를 풀면서 사용해 볼 것이다.

 

참고 : https://devowen.com/300