[Greedy] 백준 - 1202번 보석도둑

1202 보석도둑

😊 key point

대표적인 그리디 문제로 가방의 무게보다 가벼운 것들 중 최대값만 뽑아서 더하는 방법을 구현하면 풀 수 있다. 이때 시간복잡도를 고려하여 heapq를 사용해야 한다.

1. 가방의 무게 한도를 나타내는 bag, 보석의 무게와 가격을 차례로 저장한 jew 리스트를 오름차순 정렬한다.
2. 가방의 무게 bag[i] < 보석의 무게 jew[j][0]이면 heapq에 넣고 j += 1
   그렇지 않으면 while문 탈출, 뽑은 최대값 result 변수에 차례로 더한 다음 i +=1이 되는 식으로 진행된다.
3. 최대값을 뽑기 위해 jew[j][1]에 -1을 곱하였다.

😍 코드

import heapq
n,k = map(int, input().split())

jew = []

bag = []

for _ in range(n):
    jew.append(list(map(int, input().split())))

for _ in range(k):
    bag.append(int(input()))

jew.sort()  # 보석 무게 오름차순 정렬 
bag.sort()  # 가방 한도 무게 오름차순 정렬

j = 0

queue = []

result = 0

for i in range(k):
    while j < n:
        #보석의 무게가 가방 한도보다 작다면
        if jew[j][0] <= bag[i]:
            heapq.heappush(queue, -jew[j][1]) #최대값만 빼내기 위해 -1을 곱한다.
            j += 1
        #보석의 무게가 가방 한도보다 크다면 <while문 탈출>
        else: 
            break
    
    if queue:
        result += (-1) * heapq.heappop(queue) #원래의 값을 도출하기 위해 다시 -1을 곱한다.

print(result)