[코딩테스트] 백준 1202번: 보석 도둑

-문제: https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

우선순위 큐를 이용한 문제. 

스스로 풀어보면서 특정 가방에 해당하는 특정 보석을 넣고 리스트에서 없애고 싶었는데 그 방법을 몰랐다. 

구글링 해보니 조건을 만족하는 원소를 없앨 때 heapq.pop()을 이용한다는 것을 배웠다. 

다음번에는 이 방법 적용해봐야겠다 

 

-정답 풀이: 

import heapq
n,k=map(int,input().split())
s=[]
l=[]
for _ in range(n):
    s.append(list(map(int,input().split())))
for _ in range(k):
    l.append(int(input()))
l.sort()
s.sort()

cnt=0
ans=[]
for i in l:
    while s and i >= s[0][0]:
        heapq.heappush(ans,-s[0][1])
        heapq.heappop(s)
    if ans:
        cnt+= heapq.heappop(ans)

print(-cnt)

문제 푸는 아이디어는 다음과 같다.

각 가방에 담을 수 있는 최대 가치의 보석을 담되 작은 가방부터 보석을 담는다.

것을 구현할 때 최대힙과 최소힙을 사용한다. 

가방들을 용량의 오름차순으로 정렬했을 때 

각 가방에 담을 수 있는 모든 보석을 찾을때 최소힙을 사용하고

각 가방에 넣을 수 있는 보석 중 가장 가치가 큰 보석을 찾을 때 최대힙을 사용한다. 

출처: https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-1202-%EB%B3%B4%EC%84%9D-%EB%8F%84%EB%91%91-Python

[백준 1202] 보석 도둑 (Python)

• 15번: 보석의 최소 무게보다 가방의 무게와 보석의 무게가 같거나 큰 경우에만 while문 수행
• 16번: ans 리스트에 해당 보석의 가격의 음수값을 넣는다.(Heap에서는 최솟값이 맨 첫번째이고, 문제에서 구하는 수는 최댓값이기 때문에 마이너스를 붙여서 값을 넣는다)
• 17번: 보석 리스트에서 뺀다. (?)-> 다른 블로그 찾아보니 있어도 되고, 없어도 되는 코드인 것 같다. 
• 조건을 만족하는 보석의 가격들을 하나씩 더한다
• 20번은 왜 있는지 잘 모르겠음(?)-> 20,21번을 빼고 코드 돌려도 똑같이 정답이 나온다.