[백준] 1202번 보석 도둑 (Python)

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

📌 문제

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

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

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

 

📌 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

📌 출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

---

📌 풀이 방식 

첫 골드2 문제 !!

한 3시간 고민하고 ... 도저히 안 풀려서 다른 분들 블로그보고 힌트좀 얻었습니다 ,, 

 

가장 핵심이 되는 키 포인트는

🔑 최대 무게가 낮은 가방부터 보석을 채워준다

🔑 가방에 들어갈 수 있는 보석을 구할 때에는 낮은 무게를 기준으로 우선순위큐를

     가방에 들어갈 수 있는 보석에서 가장 값진 보석을 구할 때에는 높은 가격을 기준으로 우선순위큐를 사용한다

🔑 이전 가방에 들어갈 수 있는 보석은 다음 가방에도 들어갈 수 있다 (무게 낮은 가방부터 보석을 채워주기 때문에)

 

이정도 인 것 같습니다. 가장 어려웠던 부분이 3번째 키포인트인데요. 

이전 가방에 들어갈 수 있는 보석은 다음 가방에도 들어갈 수 있기 때문에 기존 입력받은 보석 배열을 사용하는게 아니라

따로 가방에 들어갈 수 있는 보석들을 담고 있는 배열을 선언해서 사용하면 됩니다 :~)

 

Q. 높은 가격을 기준으로 우선순위큐를 어떻게 사용하나요 ?

A. 높은 가격을 기준으로 우선순위큐를 사용하려면 기준이 되는 값에 - 를 붙여서 저장하면 됩니다.

---

📌 코드

import sys
import heapq
input = sys.stdin.readline

# 보석 개수 = n, 가방 개수 = k 
n, k = map(int, input().split())
jewels = []

for _ in range(n):
    m, v = map(int, input().split())
    heapq.heappush(jewels, (m, v))

bags = [int(input()) for _ in range(k)]
bags.sort()

temp = []
result = 0
# 가장 작은 가방부터 채워준다
for bag in bags:
    # 가방에 들어갈 수 있는 보석들을 temp 배열에 저장해준다
    while len(jewels) > 0 and jewels[0][0] <= bag:
        j = heapq.heappop(jewels)
        heapq.heappush(temp, (-j[1], j[0]))

    # 가방에 들어갈 수 있는 보석들 중 
    # 가장 값어치가 큰 보석을 가방에 넣어준다
    if len(temp) > 0:
        k = heapq.heappop(temp)
        result += -k[0]
    
    # 만일 보석도 없고, 가방에 들어갈 수 있는 보석도 없으면
    # 프로그램을 끝낸다
    if len(temp) == 0 and len(jewels) == 0:
        break
    
print(result)

 

jeweles 는 우선순위큐가 아니라 그냥 배열로도 사용할 수 있지 않을까해서 시도해봤는데 어김없이 시간초과 가 발생하더라구요 ㅜ

우선순위큐를 사용하는 걸 잊지 말아주세요 !!

 

엄청난 시간초과 메모리 초과 후에 통과 😭