[BOJ] 1202 보석도둑

date

Aug 5, 2023

slug

boj-1202

author

status

Public

문제 링크

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

문제

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

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

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

문제풀이

배낭과 보석을 오름차순으로 정렬하고

작은 무게를 가진 배낭이, 그 배낭보다 작거나 같은 보석 하나의 값어치가 최대가 되게끔 하면된다.

배낭보다 작거나 같은 보석들의 가치를 모두 최대힙에 넣어주고

가장 큰 가치가 가진것이 배낭에 들어갈 수 있게끔, 최대힙에서 제거해준다,

그리고 다음 배낭의 크기는 항상 이전 배낭보다 클 것이기 떄문에 최대힙에 현재 있는 값들은 모두

다음 배낭에 들어갈 수 있는 후보가 된다.

배낭보다 작거나 같은 보석들의 가치를 모두 최대힙에 넣어주면

배낭마다 들어갈 수 있는 최대 값을 logN으로 구해 줄 수 있다.

파이썬 문제풀이 코드


import sys
import heapq
input = sys.stdin.readline

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

jewelies = []
bags = []

for _ in range(N):
    M, V = tuple(map(int, input().split()))
    jewelies.append((M, V))
    
for _ in range(K):
    bags.append(int(input()))
    
    
jewelies.sort() # 가치가 큰 순서대로 정렬
bags.sort() # 크기가 낮은 순서대로 정렬

result = 0

tmp = []

for bag in bags:
    while jewelies and jewelies[0][0] <= bag: # 가방에 넣을 수 있으면
        heapq.heappush(tmp, -jewelies[0][1]) # 값 넣음 
        heapq.heappop(jewelies) # 값 제거
    if tmp:
        result -= heapq.heappop(tmp) # 가방에 들어갈 수 있는 가장 큰 값 제거
        
print(result)

시간복잡도