[백준] 1202 보석 도둑

📌문제 링크

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

💡 문제 풀이

처음엔 보석을 가치가 큰 것부터 정렬하고, 배낭도 오름차순이든 내림차순이든 정렬해서(어차피 가방에 보석 한 개만 들어가니까) 가방 무게와 보석 무게를 비교해주면 보석 가치가 큰 순서대로 넣을 수 있을 거라고 생각했다.

근데 생각은 이렇게 해놓고 막상 코드 짜려니까 손을 못 대겠어서 구글링을 했다....
모든 사람들이 우선순위 큐, 힙큐를 쓰고 있더라
언제쯤 문제를 보면 이런 생각을 할 수 있는거지

최소나 최대인 걸 뽑아내고 다음 경우에서 제외하려면 힙큐, 우선순위 큐를 써야하는 것 같다!!

✔ heapq를 쓸 때 주의할 점

여기서 주의할 점은 힙큐에 배열 값을 넣으면 바로 출력해도 정렬돼서 나오지 않는다..!!
이거땜에 왜 정렬 안되지...? 이생각함
출력할 땐 정렬돼서 안보이지만 pop을 하면 최솟값부터 나온다

그리고 heapq는 기본이 최소 힙이기 때문에 최대 힙으로 만들려면 -를 붙여 음수로 만드는 꼼수를 써야 한다 (자체적으로 숫자 순서를 바꿔줘야함)
pop해서 원래 값으로 쓰려면 당연히 -를 다시 붙여줘야한다

📋코드

# 1202 보석 도둑
import sys
import heapq
n, k = map(int, sys.stdin.readline().split())
bag = []
jewel = []

for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    heapq.heappush(jewel, [w, v])

for i in range(k):
    heapq.heappush(bag, int(input()))

result = 0
tmp = []  # 현재 가방에 담을 수 있는 무게의 보석들

for i in range(k):
    capacity = heapq.heappop(bag)

    # 현재 가방에 담을 수 있는 무게 이하인 모든 보석에 대해
    while jewel and capacity >= jewel[0][0]:
        [w, v] = heapq.heappop(jewel)
        # 보석의 가치를 힙에 넣어줌
        # 파이썬에서 heapq는 최소힙만을 지원하기 때문에, 최대힙을 만들려면 -를 붙여서 푸시
        heapq.heappush(tmp, -v)

    if tmp:
        result -= heapq.heappop(tmp)

print(result)

python3로는 시간초과 떴고 pypy3으로 통과했다

➕ 추가!!

구글링해서 본 코드라 왜 tmp를 전역변수 설정을 해주는걸까?? capacity는 가방마다 다를텐데... 그때그때 초기화를 해야되지않나?? 라고 생각했다
근데 heapq에서 빼내 쓰는거니까 가방에 담을 수 있는 무게가 가장 작은 것부터 나오니 당연히 tmp에 담긴 보석은 그 다음에 pop되어 나오는 가방에도 담을 수 있다!