[백준/Python]1202: 보석 도둑

문제

https://www.acmicpc.net/problem/1202
문제집 - BOJ 길라잡이 베타 (1)

 

알고리즘: 그리디 Greedy

---

풀이

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.
상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

 

각 가방이 K개 주어지고, 가방에 따라 담을 수 있는 최대무게값이 다르다.
가방 하나당 하나의 보석만 넣을 수 있다.
보석은 무게, 가치로 주어진다.

 

나는 다른 풀이들을 참고하여 3개의 힙을 사용했다.
먼저 힙1에는 주어진 보석들을 (무게, 가치)로 저장한다.
힙2에는 가방의 무게를 저장한다.
힙3에는 현 가방의 무게보다 적거나 같은 보석의 가치만 저장한다.

 

각 힙의 이름을

힙1 = jewl
힙2 = sack
힙3 = taken_out

라고 했을때,

 

가방의 갯수대로(K) 순회하면서, 가장 가벼운 가방부터 무거운 가방까지 꺼낸다.
현재 가방을 s라고 했을때, 's의 무게 >= jewl에서 가장 가벼운 보석의 무게'라면 보석을 꺼낸 뒤 가치를 taken_out에 추가한다.
taken_out은 최대힙으로 구성해야하므로 -가치로 저장해야한다.

 

비교를 반복하며 jewl에 남아있는 보석 중 s보다 같거나 적게 나가는것이 없다면 멈춘다.
그럼 s에 들어갈 수 있는 무게의 보석은 모두 taken_out에 들어가 있는 상태가 된다.

 

마지막으로 taken_out의 보석들 중 가장 큰 가치를 지닌 보석을 꺼내 결과값에 추가한다.
최대힙이므로 heappop했을때의 보석이 가장 큰 가치의 보석이다.

남아있는 taken_out의 보석들은 앞으로 나올 s보다 무조건 적게 나가므로, taken_out에서 꺼낸 보석들은 무조건 현재 s에 들어갈 수 있는 보석들인셈이다.

 

가방을 모두 사용할때까지 위의 과정을 반복하며, 결과값을 업데이트한다.

 

전체 코드

from sys import stdin
from heapq import heappop, heappush


input = stdin.readline

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

jewl = []
for _ in range(N):
    heappush(jewl, tuple(map(int, input().split())))

sack = []
for _ in range(K):
    heappush(sack, int(input()))

taken_out = []
ret = 0
for _ in range(K):
    s = heappop(sack)

    # (현재 가방 s >= 가장 가벼운 보석의 무게) 라면, taken_out에 -(보석의 가치)를 넣는다.
    while jewl and s >= jewl[0][0]:
        _, v = heappop(jewl)
        heappush(taken_out, -v)
    # taken_out에 보석이 존재한다면 제일 가치가 높은 보석을 빼서 ret에 추가한다.
    if taken_out:
        ret -= heappop(taken_out)

print(ret)

# 가장 작은 가방부터 큰 가방 순으로 순회하기 때문에, 현재 턴의 s는 taken_out에 존재하는 보석을 100% 넣을 수 있다.
# 딕셔너리를 사용하는 풀이도 있지만 메모리가 너무 커지게된다.

 

머릿속이 스파게티 코드화🍝될때엔 돌려보면서 푸는게 나은것같다.