IT-garden

문제

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

상덕이가 털 보석점에는 보석이 총 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

heapq 모듈은 힙큐 알고리즘 구현을 해줍니다.

heapq 모듈은 이진 트리의 최소힙 자료구조를 제공합니다.

heapq에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]을 만족하는 배열을 사용합니다.

따라서 인덱스 0인 이진 트리의 루트에 가장 작은 요소가 있습니다.

heapq.heappush(heap 이름, 추가할 원소)
heapq.heappop(heap 이름)
heapq.heappushpop(heap 이름, 추가할 원소)
heapq.heapify(리스트 이름)

heapq의 기본 함수입니다.

heappush는 힙에 원소를 추가합니다.
heappop은 가장 작은 원소를 삭제합니다.
heappushpop은 힙에 원소를 추가하고 가장 작은 원소를 삭제합니다. 이는 heappush()한 다음 heappop()을 각각 사용하는 것보다 더 유용합니다.

heapify는 리스트를 인자로 넘기면 리스트 원소들을 힙 구조에 맞게 바꿔줍니다. 새로운 리스트를 생성한 후 heappush() 함수로 원소를 하나씩 추가하는 것을 한번에 해주는 기능입니다.

import heapq

a=[]

heapq.heappush(a, 1)
heapq.heappush(a, 5)
heapq.heappush(a, 3)
heapq.heappush(a, 2)
heapq.heappush(a, 4)

# 출력>>[1, 2, 3, 5, 4]
print(a)

# 출력>>1
print(heapq.heappop(a))

b=[8,6,4,3,1,5]

heapq.heapify(b)

# 출력>>[1, 3, 4, 8, 6, 5]
print(b)