[알고리즘][Python] 백준 1202 보석 도둑 문제 풀이

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

1202번: 보석 도둑

---

문제 해석 : N개의 보석과 K개의 가방이 있다 이때 가방에는 1개의 보석만 넣을 수 있고 무게 제한이 있다. 또한 보석에는 무게와 가치가 매겨져 있다. 가장 높은 가치의 보석을 훔치는 경우의 가치의 합을 구하라

 

문제 풀이 :  정렬과 heapq를 활용해서 풀 수 있다. 배낭을 오름차순으로 정렬하고 보석은 무게를 기준으로 오름차순으로 정렬한다. for문을 통해서 가장 작은 무게를 가진 가방부터 넣을 수 있는 보석을 heapq에 가치를 삽입한다. 넣을 수 있는 모든 보석을 탐색하고 가장 위에 있는 것이 가장 가치가 큰 것이기 때문에 이를 정답에 더해준다. ( 단 이 때 heapq는 항상 최소힙이기때문에 -1를 곱해서 부호를 바꾸어 가장 큰 가치를 가진 보석이 가장 작은 수가 되도록 해준다. )

---

풀이 코드

import sys, heapq
input = sys.stdin.readline

N, K = map(int, input().split())
Q = []

jew = [list(map(int, input().split())) for _ in range(N)]
bag = [int(input()) for _ in range(K)]

jew.sort(key = lambda x: x[0])
bag.sort()

answer = 0
index = 0
for now in bag:
    while index < N and now >= jew[index][0]:
        heapq.heappush(Q, -jew[index][1])
        index += 1
    if Q:
        answer -= heapq.heappop(Q)

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.