[Python] 1202. 보석도둑(골2) / 우선순위 큐(heapq)

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

1202번: 보석 도둑

---

2. 핵심 아이디어

 

이 문제가 헷갈리는 이유는

고려해야 하는 요소가 2가지로 분할되어 있기 때문이다.

 

즉, 배낭의 무게를 고려함과 동시에

그중 가치가 최대가 되어야 한다.

 

그럼 만약 이렇게 하면 어떨까?

 

- 먼저 가방을 기준으로 담을 수 있는 보석을 우선 모두 담는다.

- 그중 가장 값비싼 보석 하나만 들고 간다.

 

백준 기준 예제 2를 통해 설명해보자

 

먼저 가방 용량을 기준으로 오름차순을 해준다.

bag= [2, 10]

 

그리고 보석 리스트에는 무게와 가치를 담아주자.

gem= [(1,65), (2,99), (5,23)]

 

 

이제 훔칠 수 있는 보석을 담을 리스트와

최종적으로 훔친 보석의 가치합인 result변수를 만들자.

tmp = []

result= 0

 

먼저 용량이 2인 가방을 기준으로 고려해보자

첫번째 보석 : 무게 1 / 가치 65 => 가능

두번째 보석 : 무게 2 / 가치 99 => 가능

세번째 보석: 무게 5 / 가치 23 => 불가능(용량초과)

 

그럼 tmp에 훔칠 수 있는 보석1과 보석2를 gem에서 빼고

그 가치들을 tmp에 담아준다.

gem= [(5,23)] => (1,65) / (2,99)빠짐

tmp= [65, 99]

 

그런데 가방한개에 하나의 보석만 훔칠 수 있지 않는가..

그러니까 가능한 리스트 중에서 가장 비싼 99를 가져간다.

result += 99

 

그럼 다음으로 용량이 10인 가방을 기준으로 고려해보자

먼저 현재 훔칠 수 있는 보석의 가치들은 이렇다.

tmp = [65]      (99는 가져감)

 

이 리스트를 초기화하지 않는 이유는

가방 용량을 오름차순으로 정렬했기 때문에

앞에 나온 가방들이 담을 수 있는 보석이라면

뒤에나온 가방들은 용량이 더 큼으로 자명하게 담을 수 있기 때문이다.

 

그렇기 때문에 이 상태에서 남은 보석들을 고려해주자

gem= [(5,23)]

보석1 : 무게 5 / 가치 23 = > 가능

 

그럼 보석1의 가치를 tmp에 담으면 다음과 같이 된다.

gem = []

tmp = [65,23]

 

이 가방도 가장 비싼 보석 1개만 가져간다. (65)

result=99 +65 => 164

---

그럼 여기서 어디에 우선순위 큐가 쓰일까?

 

바로 가장 비싼 보석을 고를 때 사용한다.

즉, 최대힙을 통해 모든 보석들의 가치를 음수값으로 저장하면

tmp =[-99 ~~] 이런 식으로 가장 비싼 보석의 가치가 가장 낮은 값이 되어 맨 앞에 오고

 

heapq.heappop을 하면 가장 비싼 보석의 가치가 음수로 나오게 된다.

 

따라서 result에 더해줄 때는 다시 음수를 씌워 더해주어야 하는 것이다.

 

코드를 바라보자

---

3. 코드

import heapq

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

gem=[]
bag=[]
for _ in range(n):
  weight, price = map(int, input().split())
  gem.append((weight, price))

gem = sorted(gem, key=lambda x: (x[0], x[1]))


for _ in range(k):
  bag.append(int(input()))

#용량별로 정렬
bag= sorted(bag)

result=0
tmp=[]

for max_weight in bag:
  while(gem and gem[0][0]<=max_weight):
    
    #가방에 넣을 수 있는 보석을 다 넣기
    heapq.heappush(tmp, -gem[0][1])
    
    #가방에 넣은 보석은 진열장에서 빼주기
    heapq.heappop(gem)

  #담을 수 있는 보석이 있다면 => 가장 비싼 보석 훔치기
  if tmp:
      result-=heapq.heappop(tmp)
      
print(result)

---

4.배운점

최대합/최소합 문제에서는 heapq를 활용한 정렬을 사용하면 시간복잡도에서 큰 이득을 본다..

 

이 풀이는 다음 블로그를 참고하여 작성하였습니다.

https://bio-info.tistory.com/195

[백준] 1202 - 보석 도둑 💎 (Python) / 골드 2 / 정렬 / 그리디

 

>>같은 논리이나 쉬운문제들

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

2075번: N번째 큰 수

 

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

2109번: 순회강연