[Python] G2_1202_보석 도둑 💎

https://www.acmicpc.net/problem/1202

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제

코드

import sys,heapq
input = sys.stdin.readline

N,K = map(int,input().split()) # 보석, 가방의 개수

# 리스트에 보석과 가방 정보를 함께 저장
lst = []
bag = 1000001 # 가방임을 나타냄 (=보석의 최대 가치보다 커야 동일한 무게에서 뒤쪽에 위치)
for _ in range(N):
    lst.append(list(map(int,input().split())))
for _ in range(K):
    lst.append([int(input()),bag]) 
# 무게가 가벼운 순으로 정렬  
lst.sort()
# 현재 가방에 들어갈 수 있는 가장 높은 보석의 가치가 힙큐 맨 앞에 위치
hq = []
res = 0
for info in lst:
    if info[1] != bag:
        heapq.heappush(hq,-info[1])
    else:
        if hq:
            res += (-heapq.heappop(hq))
        
print(res)

이 문제는 가장 가벼운 용량의 가방에 가장 큰 가치의 보석을 넣어주는 것이 포인트이다!

• 이를 위해서 lst에 보석과 가방 정보를 함께 저장해준다.

• 가방임을 나타내기 위한 변수인 bag을 100001로 설정해준다.

👉 보석과 가방이 같은 무게일 때, 가방이 보석보다 뒤에 위치하도록 보석의 최대 가치보다 크게 만들어준다.

무게가 가벼운 순으로 정렬한다.

• 이를 통해서 lst에는 동일한 무게의 보석, 가방 정보가 차례대로 들어있게 된다.

보석과 가방 정보를 가지고 최종적인 최대 가치를 구해준다.

• 보석일 경우, hq에 넣어준다. 이는 최대힙이기 때문에, 가장 큰 가치의 보석을 우선으로 보여준다.

• 가방일 경우, hq에서 가장 큰 가치의 보석을 하나 빼서 res에 가치를 합해준다.

느낀 점 & 배운 점

1. 처음에는 가장 용량이 가벼운 가방을 구하기 위해서 최소힙을 쓰고, 가장 가치가 큰 보석을 구하기 위해서 최대힙을 사용했다. 하지만 이렇게 하니 무게를 맞출 수가 없었다.

2. 결국 리스트에 함께 넣어주고 무게순으로 정렬함으로써, 가방 정보가 나왔을 때 이전까지의 보석을 무조건 넣을 수 있도록 만들어주는 것이 중요한 문제였다!

3. 정렬과 힙 큐를 적절히 사용할 수 있었던 좋은 문제였다고 생각한다.