[Python] 백준 1202번 : 보석 도둑

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

1202번: 보석 도둑

---

 문제 풀이

그리디 알고리즘 문제이다.

 

이 문제를 풀 때 가장 중요한 핵심이 있다.

가장 용량이 적은 가방에 넣을 수 있는 무게의 보석 중 가장 큰 가치를 지닌 것을 넣어야 한다는 것이다.

가장 큰 가치를 바로 찾기 위해서 max heap을 사용해준다.

지금 확인하는 용량에 부합하는 모든 보석을 넣고 max heap에서 pop 해준다.

 느낀 점

힙을 하나 더 만들면 간단하게 처리된다는 것을 생각하기까지 오래 걸렸다...

처음엔 knapsack 알고리즘인 줄 알고 풀려고 했는데 그냥 자료구조..? 문제에 더 가까운 것 같다.

 코드

import sys, heapq

N, K = map(int, sys.stdin.readline().split())
J = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
C = [int(sys.stdin.readline()) for _ in range(K)]
J.sort()
C.sort()

sum_ = 0
tmp = []

for capacity in C:
    while J and J[0][0] <= capacity:
        heapq.heappush(tmp, -heapq.heappop(J)[1])
        
    if tmp: sum_ += -heapq.heappop(tmp)
    elif not J: break
    
print(sum_)