https://www.acmicpc.net/problem/1202
요약하자면 보석을 털건데 N개의 보석이 있고 각 보석은 무게와 가치가 있다.
가방이 K개가 있고 1가방=1보석 ,가방마다 담을 수 있는 무게가 존재한다고 했을때 최대가치로 보석을 가방에 담는 문제
초반에는 2중for문을 통해 풀었다. 이문제의 정답률을 봤을때 그렇겐 풀리지 않겠구나 싶었지만 몸소 안된다는것을 눈으로 확인😂 heapq를 사용하여야 풀리는 문제다.
예제 2번을 통해 돌아가는 로직을 설명해보고자 한다.
입력 예제 2)
3 2
1 65
5 23
2 99
10
2
총 3개의 보석과 2개의 가방이 존재한다.
첫번째로 할일은 보석리스트와 가방리스트를 정렬해주는 것이다.
각각의 배열에 .sort를 해주면 다음과 같이 담긴다.
gold = [[1,65],[2,99],[5,23]] bag = [2,10]
for문을 통해 가방의 무게들을 확인하며 while문을 거치게 된다.
for i in bag: # i -> 내가 가지고 있는 가방의 무게 while gold and i >= gold[0][0]: #while gold : gold배열이 있으면서 #i >= gold[0][0] : 가방에 보석을 담을 수 있으면 heapq.heappush(temp,-gold[0][1]) #temp라는 배열에 보석의 가치를 담아주고 heapq.heappop(gold) #방금 확인한 gold배열의 원소를 삭제한다. if temp: result += heapq.heappop(temp) #temp에 가장 큰 값을 더해준다.
초기 i에는 2가 들어가 있다. while문은 보석이 존재하면서 가방에 넣을 수 있을때 돌아가게 된다. 그 결과 [0][0]의 원소를 보면 2보다 같거나 작은 [1,65]와 [2,99]가 들어갈 수 있고 [0][1]의 원소에 -를 붙여 temp에 추가한다.
for문을 1번 돈 시점에서 if temp로 넘어가게 되며 heapq특성상 가장 작은 수를 반환하므로 result에는 -99가 들어간다.
마찬가지로 돌게 되며 if문을 만났을 때 temp에는 -65,-23이 담겨있고, 이때 -65를 반환하게 되는데 가방의 무게 배열를 sort했으므로 초반에 들어갈 수 있다면 후반에도 들어갈 수 있다.
최솟값을 뽑을 수 있는 heapq를 활용해 -값을 붙여 최대값을 뽑을 수 있는 내용만 잘 기억하면 충분히 풀 수 있는 문제😎
코드
import heapq
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
gold = [list(map(int,input().split()))for _ in range(n)]
bag = [int(input()) for _ in range(k)]
gold.sort()
bag.sort()
temp = []
result = 0
for i in bag:
while gold and i >= gold[0][0]:
heapq.heappush(temp,-gold[0][1])
heapq.heappop(gold)
if temp:
result += heapq.heappop(temp)
print(-result)
