BOJ - 보석 도둑 [1202]

문제

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

1202번: 보석 도둑

 

핵심 로직

허용량이 가장 작은 가방부터 차례대로 보석 무게들을 비교하여,
담을 수 있는 보석후보를 보석 가격을 우선순위로 최대힙에 넣고,
각 가방에 담을 수 있는 가장 높은 보석 가격들의 합을 구한다.

사전작업: 보석(무게, 가격)리스트, 가방(허용량)리스트 오름차순 정렬
힌트: 오름차순으로 정렬되어 있는 리스트의 경우,
           바로 heapq.heappop() 혹은 heapq.heappush()를 사용해도 문제없다.

 

정답 코드 - [시간복잡도: O(N*logN)]

import sys, heapq

input = sys.stdin.readline

N, K = map(int, input().split())
gem_list = [list(map(int, input().split())) for _ in range(N)]
bag_list = [int(input()) for _ in range(K)]

max_heap = []
max_price = 0
gem_list.sort()  # O(N*logN)
bag_list.sort()  # O(N*logN)
for bag in bag_list:  # 사실상 O(N)
    while (True):
        if (len(gem_list) == 0) or (gem_list[0][0] > bag):
            if (len(max_heap) != 0):
                max_price += -1 * heapq.heappop(max_heap)
            break
        weight, price = heapq.heappop(gem_list)
        heapq.heappush(max_heap, -1 * price)
        
print(max_price)