[백준] 보석 도둑 파이썬 풀이

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

---

 

문제 접근

◇ 상덕이가 훔칠 수 있는 보석의 최대가격을 구하는 문제입니다. 보석의 무게(M)와 가격(V) 그리고 상덕이가 가지고 있는 가방의 무게(C)가 주어집니다. 상덕이의 가방에는 보석이 딱 한 개만 들어갈 수 있고 가방에 들어갈 보석은 가방의 무게보다 작아야 합니다. ( C >= M )

 

◇ 상덕이가 훔칠 수 있는 보석 가격의 합의 최대값을 구해야 하고, 가방에 들어갈 수 있는 무게가 제한점이라는 것에서 Heapq로 풀어야 할 것 같은 기분이 들었다.

 

◇ 처음에는 무거운 가방부터 처내는 것을 목표로, 무거운 보석 중에 가장 비싼 보석을 가방에 넣는 로직을 생각했으나

가장 무거운 보석을 넣는게넣는 게 최선이 아니라는 생각이 들었다. 가장 무거운 보석이 가장 비싸다는 보장도 없고, 공간의 여유를 최소화하기 위해 최솟값부터 넣는 게 옳다는 생각이 들었습니다.

 

반례

 

---

 

 

문제 풀이 (With Python)

import sys
import heapq

N, K = map(int, sys.stdin.readline().split(" "))
jewel = []
for _ in range(N):
    M, V= map(int, sys.stdin.readline().split(" "))
    heapq.heappush(jewel, (M, V))

bag = []
for _ in range(K):
    C = int(sys.stdin.readline().rstrip())
    heapq.heappush(bag, C)

save_price = []
answer = 0
for a in range(K):
    size_of_bag = heapq.heappop(bag)
    while jewel:
        if size_of_bag >= jewel[0][0]:
            heapq.heappush(save_price, -jewel[0][1])
            heapq.heappop(jewel)
        else:
            break
    if save_price:
        answer -= heapq.heappop(save_price)

print(answer)

 

◇ 보석은 무게를 기준으로 오름차순으로 Heapq에 넣어주고, 가방도 똑같이 오름차순 순으로 Heapq에 넣어주었습니다.

 

◇ 가방에 넣을 보석을 찾기 위해 가방 수 만큼 for문을 돌리고, 보석을 넣을 가방을 heapop으로 꺼내옵니다.

 

◇ 가방에 넣을 수 있는 보석들이 여러개가 있을 수 있습니다. 그중 최고 가격을 거르기 위한 save_price라는 Heapq를 선언해줍니다.

 

◇  꺼내온 가방의 무게를 jewel heapq의 가장 앞에 있는 보석의 무게와 비교해서, 가방에 넣을 수 있다면 save_price에 넣어줍니다. 이때, save_price 에는 가장 비싼 가격이 먼저 앞에 있어야 하므로, 가격에 - 를 곱합니다. (파이썬에서는 min heapq만 지원하기 때문에, max값이 먼저 오는 heapq를 만들기 위해서 값에 -를 곱해서 큰 값이 앞에 올 수 있도록 설정해 줍니다.)

 

◇ 현재 가방에 넣을 수 있는 보석이 없다면, break문을 타고 밖으로 나옵니다. break문을 타고 나왔을 때, save_price에 보석 가격이 저장되어 있다면 save_price에 제일 앞에 있는 값을 꺼내 (앞에 있는 값이 제일 큰 값이기 때문) answer에 더해줍니다. (현재 save_price에 값이 -가 곱해져 있기 때문에 수식에서는 -를 해주는 것으로 합을 구했습니다.)