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

1202번: 보석 도둑

 

📝 문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

📜 풀이

• 최대힙(Max Heap)을 사용하여 구현하면 시간복잡도를 줄일 수 있어, 시간초과를 피할 수 있다.
• 구현 방식은 다음과 같다.
  • 보석과 가방에 대한 정보가 저장된 배열을 오름차순 정렬한다.
  • 이후 모든 가방에 대하여 아래 과정을 반복해서 수행한다.
    • 현재 가방에 들어갈 수 있는 보석을 모두 최대힙에 저장한다.
      • 최대힙에 저장한 보석은 배열에서 제거한다.
    • 이후, 최대힙에서 pop 연산을 수행하여 현재 가방에 들어갈 수 있는 보석들 중 가치가 가장 높은 보석의 가치를 뽑아낸 후 출력값에 더해준다.
    • 위 과정중에 최대힙에는 이전 가방에 대한 반복문 수행시에 저장된 값이 존재할 수 있으며, 이는 즉 이전 가방에 들어갈 수 있는 보석은 현재 가방에도 들어갈 수 있음을 의미한다.(이전에 오름차순 정렬하였기 때문)

 

💻 소스코드

import sys
import heapq
input = sys.stdin.readline

n, k = map(int, input().split())
jewels = [list(map(int, input().split())) for _ in range(n)]
bags = [int(input()) for _ in range(k)]

# 무게 순으로 정렬
jewels.sort()
bags.sort()

ans = 0
max_heap = []

# 모든 가방에 대해서 반복
for weight in bags:
    # 현재 가방에 들어갈 수 있는 보석을 모두 최대힙에 저장
    while jewels and jewels[0][0] <= weight:
        heapq.heappush(max_heap, -jewels[0][1])
        heapq.heappop(jewels)   # 최대힙에 저장된 보석은 배열에서 제거
    if max_heap:    # 이전 가방에 들어갈 수 있는 보석은 현재 가방에도 들어갈 수 있음
        # 현재 가방에 들어갈 수 있는 보석들 중 가치가 최대인 보석을 넣음
        ans += heapq.heappop(max_heap)

print(-ans)