[Python 3] BOJ - 1202 "보석 도둑"

 # 문제 링크 : https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

# 풀이 :

가방에 보석을 단 하나만 담을 수 있기에 개인적으로 이 문제의 핵심은 문제의 해당 조건을 보고 그리디 알고리즘임을 생각하는 것과 자료구조로 최대 힙을 쓰는 것이라 생각한다. 우선 이 문제는 언뜻 대표적인 다이나믹 프로그래밍 문제인 '냅색 알고리즘(Knapsack algorithm)'과 얼핏 비슷해 보이나, 차이점은 냅색 알고리즘은 해당 가방의 한도를 벗어나지 않는 선에서 가방의 가치가 최대로 하는 물건들을 여러개 고르는 것이지만, 이 문제는 가방의 무게를 벗어나면 안되는 점은 비슷하지만 결정적인 차이점은 단 하나의 물건만을 담을 수 있다는 것이다.

<그림 1. 가방이 1개 존재하는 경우>

  위의 예시에서 당연히 1개만 담을 수 있으므로 1원차이가 나는 3번째 보석을 담는 것이 최적해이다. 아래의 예시는 개방이 2개 이상있는 경우를 나타낸 것이다. 만일, 그림의 경우와 달리 두번째 4g짜리 가방에 9998달러짜리 보석을 넣는다면 전체 최적이 아니기 때문에(이 경우 첫번째 1g짜리 가방과 10g짜리 가방은 최적해를 담았다고 가정) 오답이다. 따라서 가방의 한도를 초과하지 않는 보석 중 가장 큰 가치의 보석을 담아야하고, 추가적으로 용량이 작은 가방부터 큰 가방 순으로 배치하는 것이 효율적이다. 

< 그림 2. 가방이 복수개 존재할 경우>

 그러나 그림 1에서 보듯, 무게가 같은데 가치가 다른 경우가 존재하고, 무게가 크더라도 반드시 가치가 크지 않기 때문에, 단순히 리스트에 저장한다면, 각 가방의 경우마다 보석의 정보를 for문으로 돌아야 하므로 시간초과를 피할 수 없다. 따라서, 보석의 가치를 기준으로 최대힙을 구성한다면 무게가 n일때 가장 큰 가치를 가지는 보석을 O(log N)만에 구할 수 있으므로 시간안에 정답을 구할 수 있다. 

 

 # 코드

# 최대힙을 구현하기 위해 heapq 모듈 import
import sys, heapq
n, k = map(int,sys.stdin.readline().split())
gem_list = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# temp : 최대힙을 만들어 주기 위해 빈 리스트 생성
temp = []
ans = 0

# 가방 입력
for i in range(k):
    a = int(sys.stdin.readline())
    # [가방의 무게, 가방의 가치] : 가방은 보석들과 구분 되기 위해 보석의 최대 가치보다 더 크게
    # 설정하거나 -1로 설정함으로서 해당 원소가 가방임을 알려준다
    gem_list.append([a,2000000])

# 무게 순 정렬
gem_list.sort()

for i in gem_list:
    # 가방이 아니라면 보석이므로 최대 힙에 담는다
    if i[1] != 2000000:
        # heapq는 최소힙이므로 넣을 때 -1을 곱해 최대힙으로 변형시킨다
        # 자세한 설명은 heapq 모듈을 검색하는것을 추천한다
        heapq.heappush(temp, (-1 * i[1], i[1]))
    else:
        # 만일 가방의 갯수가 보석보다 많다면 pop할 수 없으므로 예외처리
        try:
            ans += heapq.heappop(temp)[1]
        except:
            pass
print(ans)