[백준] 보석 도둑 / 1202번 / 파이썬 / Python / heapq/ 힙큐

💡solutions 

💬 heapq모듈을 사용하여 최소힙, 최대힙 자료구조를 사용하였음.

💬 보석들은 무게가 작은 순서대로 뽑힐 수 있도록 최소힙으로 구현

💬 가방은 제한된 무게를 기준으로 가벼운 것부터 무거운 순으로 나오도록 오름차순 정렬

💬 for 반복문을 통해 작은 무게 제한을 가진 가방부터 꺼내와서 제한된 무게보다 가벼운 보석들을 임시 리스트인 tmp에 모두 담아둔다 -> 이때 주의할 점은 추후 tmp에서 가장 비싼 애들부터 순서대로 뽑을 수 있게 가격에 마이너스 부호를 붙여 tmp 리스트에 heappush로 넣어준다. (이게 바로 최대힙 구현하는 방법)

💬 가방에 담을 수 있는 보석 중 가장 제일 비싼 가격의 보석을 뽑아서 answer에서 빼준다 -> 애초에 보석 가격을 음수로 넣어놨기 때문에 answer에서 빼야지 더하는 개념이 된다.

 

📘 heap에 대해 알아보자 힙(heap)이란? 힙은 특정한 규칙을 가지는 트리로,  최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 힙에는 두 가지 종류가 있는데, 최소 힙(Min Heap) : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙(Max Heap) : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

최소힙과 최대힙

👨‍💻code 

import sys
import heapq
input = sys.stdin.readline
n, k = map(int, input().split())
jewelry = []
for i in range(n):
    weight, price = map(int, input().rstrip().split())
    heapq.heappush(jewelry, [weight, price])
bags = [int(input()) for _ in range(k)]
bags.sort()   # 가벼운 것부터 무거운 순으로 정렬

answer = 0
tmp = []
for bag in bags:
    while jewelry and bag >= jewelry[0][0]:   # 가방에 담을 수 있는 최대 무게보다 가벼운 보석들을 모두 담기
        heapq.heappush(tmp, -heapq.heappop(jewelry)[1])
    if tmp:
        answer -= heapq.heappop(tmp)
    elif not jewelry:
        break
print(answer)

 

 

📌description 

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)

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

출력

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

---