[백준] 1202번 - 보석 도둑

1차 시도 - 틀렸습니다.

최댓값을 더해줘야 한다 + 정렬작업 => 최대 힙이 생각났다.
maxheap을 활용하여 문제를 해결할 수 있을 것이라고 생각했다.

# 보석 도둑
import sys
import heapq

N,K = map(int,sys.stdin.readline().split())
jewerly = list()
bags = list()

for _ in range(N):
    M,V = map(int,sys.stdin.readline().split())
    jewerly.append([M,V])
jewerly.sort(key = lambda x : x[1],reverse=True) # 보석 가격을 기준으로 내림차순 정렬

for _ in range(K):
    bags.append(int(sys.stdin.readline().strip()))
bags.sort() # 최대무게가 작은 가방부터 배정해줘야함 -> 오름차순 정렬

result = []
for bag in bags:
    print(bag)
    for i in range(N):
        if bag > jewerly[i][0]:
            heapq.heappush(result,-jewerly[i][1])
            break
        print(result)
print(-sum(result))

최종 코드

스터디를 통해 방법을 알게 되었다.
heapq의 heappop을 통해 최솟값을 뽑아내서 답을 구하는 방식이다.

# 보석 도둑
import sys
import heapq

N,K = map(int,sys.stdin.readline().split())
jewerly = []
bags = []

for _ in range(N):
    M,V = map(int,sys.stdin.readline().split())
    heapq.heappush(jewerly,[M,V])

for _ in range(K):
    bags.append(int(sys.stdin.readline()))
bags.sort()

result = []
money = 0

for bag in bags:
    while jewerly and bag >= jewerly[0][0]:
            [m,v] = heapq.heappop(jewerly)
            heapq.heappush(result,-v)
    if result:
        money -= heapq.heappop(result)
    elif not jewerly:
        break
print(money)

> https://docs.python.org/ko/3/library/heapq.html
heappop = 가장 작은 값을 pop한다