[BOJ-1202] 보석 도둑 (Python)

🤒 문제

BOJ-1202 보석 도둑

💊 풀이

아.. 이거 시간초과 때문에 엄청나게 오래 걸렸다. 푼 방법은,

1. 보석을 무게 기준으로 최소힙으로 만든다.

2. 가방은 오름차순으로 정렬한다.

3. 수용 무게가 가벼운 가방 순으로 포문을 돈다.

4. while문을 돌며 보석의 무게가 가방 무게보다 가볍다면 가격 기준 최대힙인 possible에 넣는다.

5. 이때 보석을 가방에 담을 수 있는데, 바로 담지 않는 이유는, 최대한 가벼운 가방에 무거운 보석을 넣어 가방을 낭비하지 않기 위함이다.

6. 보석 무게 기준으로 최소힙을 만들었기 때문에 보석의 무게가 가방의 무게보다 무거워지면 while문이 끝난다.

7. 가방에 수용 가능한 보석이 있다면 가격이 가장 비싼것을 pop() 하여 최종 가격에 더한다.

8. 그럼 가방 for문이 끝나고 다음 가방에 대한 for문이 시작되는데, 이때 그전 가방보다 무조건 무거운 가방이므로 possible에 있는 보석들은 전부 다 담을 수 있는 것이 된다. 똑같은 논리로 possible에 보석을 더 추가하고, 또 가격이 가장 비싼것을 선택하면 된다.

• heapq 모듈에 대해 정리한 글

✨ 소스코드

import heapq
import sys

N, K = map(int, sys.stdin.readline().split())
jewels = []
bags = []
sum = 0

# jewels는 무게 기준 최소힙
for _ in range(N):
    M, V = map(int, sys.stdin.readline().split())
    heapq.heappush(jewels, (M, V))

bags = [int(sys.stdin.readline()) for _ in range(K)]
bags.sort() # 가방은 오름차순 정렬

possible = []

for bag in bags:
    while jewels and bag >= jewels[0][0]:
        m, v = heapq.heappop(jewels)
        # 담을수 있는 것은 가격 기준 최대힙
        heapq.heappush(possible, -v)
    if possible:
        sum += -heapq.heappop(possible)

print(sum)