[백준] 1202번 보석 도둑

문제

각 보석의 무게, 가격
각 가방의 수용량이 주어질 때 훔칠 수 있는 최대 가격을 구해라.
단, 각 가방은 1개의 물건만 가져갈 수 있다.

ex)

n, k
3  2
무게, 가격
1	  65
5	  23
2	  99
수용량
10
2

한 개의 가방은 한 개의 보석만 가져갈 수 있다는 조건으로 인해 그리디 풀이방법을 사용할 수 있다.

사고과정은 다음과 같다.
가방에 넣을 수 있는 모든 경우를 힙으로 관리하면 된다.
한 가방에 보석 A를 넣을 수 있으면 넣고, 보석 B도 넣을 수 있으면 B도 넣어보는 것이다.

[1번가방 보석A, 2번가방 보석B]
[1번가방 보석B, 2번가방 보석A]

이렇게 전부 구해보고 더 가격이 높은 쪽을 고르면 된다.
하지만 이 때 주의할 점이 있다.

예를 통해 살펴보자.

보석 A -> 무게 5 가격 50
보석 B -> 무게 15 가격 20

가방 a -> 수용량 10
가방 b -> 수용량 20

일 때
가방 b가 보석 A를 가져가게 되면 이 경우에는 최대가격을 얻는 방법이 아니다.
가방 b가 보석 A를 가져가면 가방 a는 어떠한 보석도 챙길 수 없다.
이 때 얻을 수 있는 가격은 50이다.

하지만 가방 b가 보석 B를 가져가면 가방 a는 보석 A를 챙길 수 있고, 얻을 수 있는 가격은 70이다.

즉, 모든 경우를 따져주되 무조건 최대 가격을 얻을 수 있게 조건을 만들어 주어야 한다.
그러면 어떻게 조건을 걸어야 할까?

가방의 수용량을 오름차순으로 정렬해주면 된다.
그러면 위와 같은 경우가 발생하지 않는다.

1. 가방 오름차순 정렬을 통해 항상 최대가격을 가져갈 수 있게 만들기
2. 가방마다 보석을 챙기는 모든 경우에 대해 힙 만들기

자세한건 코드를 통해 살펴보자.

전체코드

import sys
import heapq
input = sys.stdin.readline

n, k = map(int, input().split())
gemList = []
for _ in range(n):
	# 보석무게를 오름차순 하는 이유
    # 모든 보석에 대해 검사하며 넣을 수 있으면 넣어햐는데
    # 오름차순 되어있어야 넣고빼기 편함
    # 안되어있으면 귀찮아짐
    w, v = map(int, input().split())
    heapq.heappush(gemList, (w, v))
knapsackList = sorted([int(input()) for _ in range(k)])
packageList = []
answer = 0

for capa in knapsackList:
	# 현재 가방으로 챙길 수 있으면 챙김
    while gemList and capa >= gemList[0][0]:
    	# 최대 힙 구성
        heapq.heappush(packageList, -heapq.heappop(gemList)[1])
    if packageList:
    	# 넣어줄 때 -를 붙였으니 다시 -를 붙임
        answer -= heapq.heappop(packageList)

print(answer)