알고리즘 스터디 - 백준 1202번 : 보석 도둑

문제 해석

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하라

입력

1. N, K : 보석 개수, 가방 개수
2. M, V : 보석의 무게, 보석의 가격
3. C : 각 가방의 담을 수 있는 최대 무게(근데 각 가방에는 한 개의 보석만 넣어야 함)

어떤 알고리즘을 써야할까?

일단 당장 생각나는 알고리즘은 동적계획법의 배낭문제를 적용하는 것이다. 근데 기존 배낭 문제와의 차이점은 기존 문제는 하나의 가방에 가격을 최대로 하도록 보석을 여러개 집어 넣는 거지만 이번 문제는 각 가방에 하나씩 넣는 거라 쉬울 수 있으면서 어려울 수 있다.

만약 보석의 가치를 최대로 하려면 보석의 가격을 기준으로 리스트를 정렬하고 가방의 무게에도 우선순위를 넣어 거기에 맞춰서 넣으면 될 것 같다. 그리디 알고리즘도 한번 사용해보자.

알고리즘 코드

import heapq

N, K = map(int, input().split())

jewelry = []
for _ in range(N):
    M, V = map(int, input().split())
    heapq.heappush(jewelry, [M, V])

bag = []
for _ in range(K):
    C = int(input())
    heapq.heappush(bag, C)

answer = 0
enable_jewelry = []

for _ in range(K):
    c = heapq.heappop(bag)

    while jewelry and c >= jewelry[0][0]:
        [w, v] = heapq.heappop(jewelry)
        heapq.heappush(enable_jewelry, -v)
    
    if enable_jewelry:
        answer -= heapq.heappop(enable_jewelry)
    elif not jewelry:
        break

print(answer)