백준 1202번 보석 도둑

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

실패이유: 구현실패

import heapq

jewel_cnt, bag_cnt = map(int, input().split())

jewels = []                                         # 보석은 (보석 무게, 보석 가격) 튜플로 저장
for _ in range(jewel_cnt):                          # 보석을 무게순으로 정렬
    weight, price = map(int, input().split())
    jewels.append((weight, price))
jewels.sort(reverse=True)                           # pop 하기 위해 역순으로 뒤집는다. (가벼운 보석이 뒤로간다.)

bags = []
for _ in range(bag_cnt):                            # 들 수 있는 가방 무게를 무게순으로 정렬
    bags.append(int(input()))
bags.sort()

liftable = []                                       # 현재 가방이 들 수 있는 보석들을 담는 최대 힙
total_steal_price = 0
for bag in bags:
    while jewels and bag >= jewels[-1][0]:          # 현재 가방이 담을 수 있는 보석들만 꺼내서 최대힙에 저장
        _, price = jewels.pop()
        heapq.heappush(liftable, -price)            # 가격만 저장 (무게는 상관없음)

    if liftable:
        total_steal_price -= heapq.heappop(liftable)    # 가장 비싼 보석을 최대힙에서 꺼낸다.

print(total_steal_price)

• 보석을 훔쳐 최대 이익을 얻으려면, 현재 가방이 들 수 있는 무게내에서 최대로 비싼 보석을 훔쳐야 한다.
  
  
• 가방에 담을 수 있는 최대 무게를 오름차 순으로, 보석 무게를 내림차 순으로 정렬한다.
  • 현재 가방에 담을 수 있는 최대 무게 이하의 보석들을 모두 liftable 최대힙에 넣는다.
  • 그 후, 가장 가격이 비싼 보석을 현재 가방에 넣는다.
  • 이를 반복하여 최대 이익을 얻을 수 있다.
    
    
• (보석 개수 N + 가방 개수 K) 만큼 힙에서 넣고 빼므로 총 시간 복잡도는 O((N+K)logN) 이다.

출처: 코드플러스 - 알고리즘 중급 1/3 강의
https://code.plus/course/43