[Python/파이썬] 백준 1202번: 보석 도둑

문제

 

풀이

가방과 보석을 정렬한 후, 각 가방에 넣을 수 있는 보석 가격의 최대 값을 구한다.

 

1. 초기 값

보석

무게	1	2	5
가격	65	99	23

가방

무게	2	10
소유한 보석의 가격	0	0

 

2. 첫 번째 가방(2)에 들어갈 수 있는 보석을 우선순위 큐에 저장

보석

무게	5
가격	23

(배열 보석에서 무게가 1, 2인 값을 빼내어 우선순위 큐에 저장함)

 

우선순위 큐 (기준 : 가격)

무게	2	1
가격	99	65

(첫 번째 가방의 무게는 2이고, 2보다 작은 보석들을 우선순위 큐에 넣음)

 

가방

무게	2	10
소유한 보석의 가격	99	0

(가장 큰 값인 99를 가방(2)에 추가)

 

우선순위 큐 (기준 : 가격), 첫 번재 가방에 가격이 99인 보석을 넣어줬으므로 pop

무게	1
가격	65

 

3. 남은 보석 리스트에서 가방(10)에 들어갈 수 있는 보석을 빼내어 우선순위 큐에 저장

보석

무게
가격

 

우선순위 큐

무게	1	5
가격	65	23

 

가방

무게	2	10
소유한 보석의 가격	99	65

 

자세한 건 코드 참고

코드

import sys, heapq
input = sys.stdin.readline

n, k = map(int, input().split())
jewelry = [list(map(int, input().split())) for _ in range(n)]
bags = [int(input()) for _ in range(k)]
jewelry.sort()
bags.sort()
tmp = []
result = 0
for bag in bags:
    while jewelry and bag >= jewelry[0][0]:
        heapq.heappush(tmp, -jewelry[0][1])
        heapq.heappop(jewelry)
    
    if tmp:
        result += heapq.heappop(tmp)
    elif not jewelry:
        break

print(-result)

 

마무리

3시간 가량 고민했지만 답이 나오지 않아 구글링 했다...