[백준 BOJ / Python] 1202번 보석 도둑

문제

n개의 보석의 무게(m)와 가격(v) 정보가 주어지고, m개의 가방이 최대 담을 수 있는 무게(c) 정보가 주어졌을 때, 가질 수 있는 보석의 최대 가격을 구하는 문제이다.

이때 한 개의 가방에는 한 개의 보석만 넣을 수 있다.

풀이

• 우선순위 큐를 사용하여 문제를 풀 수 있다. 보석과 가방의 무게를 비교하고 담을 수 있는 보석이라면 가장 큰 가격의 보석을 담도록 하는 것이다.
• 먼저 보석의 정보를 얻을 때, 같은 무게를 가진 보석이 다수 존재할 수 있음으로 딕셔너리 자료구조에 담는다.
  • 딕셔너리로 관리하는 것이 메모리가 조금 늘지만 더 빠른 속도를 보여준다. 
• 한 개의 가방에는 한 개의 보석만 들어가기 때문에 보석의 최대 무개(1000000)와 비교해서 넘어가는 것은 최대 무게로 대체한다.
• 보석의 무게가 큰 것부터 가방에 넣어보기 위해 내림차순 정렬한다.
• 가방은 무거운 큰 것부터 비교하고 제거하기 위해 오름차순으로 정렬한다.
• pq는 가방에 담을 보석들을 관리해 주는 우선순위 큐다.
• 무게가 큰 보석부터 for문을 돌아서, 가방에 보석을 넣을 수 있다면 가방을 제거하고 현재 보석을 pq에 넣는다.
• 같은 무게의 다른 가격의 보석들을 비교해서 현재 pq에 담겨있는 보석가격의 최솟값보다 현재 보석가격이 크다면 바꿔준다. 즉, 가장 큰 가치의 보석들만 pq에 담을 수 있도록 한다.
• 마지막까지 pq에 담겨있는 보석들의 합을 구하면 최대 가격을 구할 수 있다.

Python 코드

import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
n,k = map(int, input().split())
gems = defaultdict(list)
for _ in range(n):
    m,v = map(int, input().split())
    gems[m].append(v)
# 보석의 최대 무게가 1000000라서 더 큰 가방을 볼 필요 없음
bags = [min(1000000,int(input())) for _ in range(k)]
gems_w = sorted(gems.keys(),reverse=True)
bags.sort()
pq = []
for w in gems_w:
    for v in gems[w]:
        if bags and bags[-1] >= w:
            bags.pop()
            heapq.heappush(pq,v)
        elif pq and v > pq[0]: 
            heapq.heappop(pq)
            heapq.heappush(pq,v)
print(sum(pq))

 

문제출처

1202번: 보석 도둑