파이썬 | 백준 | 1202 | 보석 도둑

 

solution

1. 힙 이용.

    1) 가치 - 최대힙을 이용하여 pop하고 무게가 배낭의 수용 가능한 무게보다 작으면 결과에 더한다.

    2) 배낭의 무게 - 최소힙을 이용하여 수용 가능한 무게가 작은 것부터 담을 수 있는 최대 무게를 구한다.

→시간초과

# 1202, 보석 도둑
import sys
import heapq
N, K = map(int, sys.stdin.readline().split())

jewels = []
bags = []
for _ in range(N):
    M, V = map(int, sys.stdin.readline().split())   # 무게, 가격
    heapq.heappush(jewels, ((-V, V), M))
for _ in range(K):
    heapq.heappush(bags, int(sys.stdin.readline()))

res = 0
while bags:
    bag = heapq.heappop(bags)
    tmp = []
    while jewels:
        jewel = heapq.heappop(jewels)
        if jewel[1] <= bag:
            res += jewel[0][1]
            break
        else:
            heapq.heappush(tmp, jewel)
    while tmp:
        heapq.heappush(jewels, heapq.heappop(tmp))

 

solution

최소힙 이용 - 무게 기준

# 1202, 보석 도둑
import sys
import heapq
N, K = map(int, sys.stdin.readline().split())

jewels = []
bags = []
for _ in range(N):
    M, V = map(int, sys.stdin.readline().split())   # 무게, 가격
    heapq.heappush(jewels, (M, V))
for _ in range(K):
    heapq.heappush(bags, int(sys.stdin.readline()))

res = 0
jewels_able = []

while bags:
    bag = heapq.heappop(bags)

    while jewels and bag >= jewels[0][0]:
        heapq.heappush(jewels_able, -heapq.heappop(jewels)[1])
		# print(jewels_able)
        
    if jewels_able:
        res += -(heapq.heappop(jewels_able))
    elif not jewels:
        break

print(res)

# print(jewels_able)

담을 수 있는 무게 중 가치가 가장 큰 것이 먼저 pop된다.

문제 출처 www.acmicpc.net/problem/1202

1202번: 보석 도둑