백준알고리즘 - 1202번 보석 도둑 - 파이썬(Python)

문제

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

상덕이가 털 보석점에는 보석이 총 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 heapq
import sys
input = lambda : sys.stdin.readline().strip()

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

a=[]

for i in range(n):
    m,v=map(int,input().split())
    heapq.heappush(a, [m,v])

b=[int(input()) for i in range(k)]
b.sort()

c=0
p=[]

for i in range(k):
    capa=b[i] # 현재 가방에 담을 수 있는 무게

    while a and capa >= a[0][0]: # 가방에 담을 수 있는 a에 있는 모든 보석
        [m,v]=heapq.heappop(a) 
        heapq.heappush(p, -v) # 값을 -로 넣기, 최대힙 만들기 

    if p: # 넣을 수 있는 보석이 있는 경우
        c -= heapq.heappop(p)
    elif not a: # 가방에 넣을 수 있는 보석이 없는 경우
        break

print(c)

heapq이용 : heapq는 이진 트리의 최소힙 자료구조 제공합니다.

 

**백준에서 import queue가 안되서 PriorityQueue를 사용하면 런타임 에러가 납니다.

 

1. 각 보석의 정보 m과 v를 heapq에 담습니다. 이진 트리는 m이 작은 것부터 최소힙으로 구성됩니다.
2. 가방에 담을 수 있는 최대 무게들을 입력받아 오름차순으로 정렬합니다.
3. 각 가방에 대해 담을 수 있는 보석을 검사하기 위한 for문을 실행합니다.
4. heapq a가 있고 a에 있는 최소 무게(a[0][0])보다 가방(capa)이 더 큰 경우 while문을 수행합니다.
4-1. heapq a에서 가장 작은 값을 받아 heapq p에 -v를 넣습니다. (최대힙으로 만드는 것)
4-2. heapq a에서 하나씩 빼서 while 조건을 만족시키면 계속 while문을 실행합니다.
5. 가방에 들어갈 수 있는 보석이 담긴 heapq p가 있다면 heapq p의 가장 작은 값을 출력해 c에 더합니다.(최종으로 가방에 넣는 것)
(heapq p에 넣을 때 가방의 가치를 -로 넣었기 때문에 가장 가치가 큰 값이 -로 나옵니다.
그래서 c에서 빼줍니다.)
6. 가방의 개수만큼 for문을 반복하여 보석의 최대 가격을 구합니다.

 

---

백준 알고리즘 1202번 : https://www.acmicpc.net/problem/1202

1202번: 보석 도둑