백준 문제풀이 - 1202 번

링크 -> https://www.acmicpc.net/problem/1202

1. 요약 및 풀이방법

보석 도둑이 보석의 갯수, 무게, 가격을 고려하여,
가져간 가방에 최대한 높은 가치의 보석들을 담아 나오는 방법을 찾는 문제입니다.

보석의 무게와 가방의 무게를 오름차순으로 정렬하였고,
현재 가방 까지 넣을 수 있는 보석 중 가장 값이 높은 보석들만 골라 담았습니다.

이를 위해 heapq 모듈을 사용하여 문제를 해결하였습니다.
아래의 코드에서 temp_bag에는 현재 가방 까지 넣을 수 있는 모든 보석들의 값어치가 들어 있습니다.
예를 들어 가방들의 무게가 각각 [1, 5, 10] 이고 현재 가방의 무게가 5 이면,
5 보다 무게가 같거나 가벼운 보석들이 모두 temp_bag에 들어가고,
이들 중 가장 비싼 보석만 max_heap을 이용하여 꺼내는 방법입니다.

2. Code

import sys
import heapq

def main():
    N, K = map(int, input().split())

    jewels = []
    for _ in range(N):
        weight, value = tuple(map(int, sys.stdin.readline().rstrip().split()))
        heapq.heappush(jewels, (weight, value))

    bags = [int(sys.stdin.readline().rstrip()) for _ in range(K)]
    bags.sort()

    temp_bag = []
    total_value = 0
    for bag in bags:
        while jewels and jewels[0][0] <= bag:
            heapq.heappush(temp_bag, -heapq.heappop(jewels)[1])
        if temp_bag:
            total_value -= heapq.heappop(temp_bag)
        elif not jewels:
            break

    print(total_value)


if __name__ == "__main__":
    main()

3. 학습 내용

2109_순회 강연 문제와 유사하게 heapq 모듈을 사용한 문제입니다.

하지만 이 문제에서 heapq 모듈에서 이용할 수 있는 두가지 개념을 더 학습할 수 있습니다.

1. max_heap 사용하기.
   heapq 모듈은 기본적으로 최소 힙(min heap)으로 동작합니다.
   하지만 위 문제에서는 가장 값이 큰 보석을 꺼내야 하기 때문에 가장 큰 값을 pop 해야 합니다.
   이를 위해 heappush 함수에 음수를 취해 넣어주게 되면 순서를 반대로 바꿀 수 있습니다.

2. heapq list의 정렬.
   heapq 모듈의 리스트는 기본적으로 [0] 인덱스의 최소값만 보장합니다.
   따라서 가장 작은 값을 확인하고 싶을 땐, some_list[0] 로 확인할 수 있습니다.
   하지만 두번째로 작은 값을 확인하고 싶다고 해서 some_list[1] 로 확인하면 오류가 발생합니다.
   왜냐하면 heappop 함수를 호출하여 원소를 삭제할 때, 재배치를 통해 최소값을 [0] 인덱스에 위치시키기 때문입니다.

4. 결과