[ProblemSolving] 백준 1202 보석 도둑 문제풀이

백준 1202 보석 도둑 문제 해설을 알아보겠다. 해설은 다음 링크를 확인하면 된다. 문제 해설

1202번: 보석 도둑

해당 문제는 그리드 유형의 문제로 최적의 해를 찾기 위한 방법을 생각해야 한다. 해당 문제는 모든 경우의 수를 확인하여서 해결할 수도 있지만 최악의 경우에는 30만 X 30만 = 900억 번의 연산을 진행하여한다. 따라서 모든 경우의 수를 확인하지 않고, 버릴 수 있는 조건을 생각해야 한다. 문제 해결 과정은 다음과 같다. bags는 가방 정보, data는 보석의 가치와 무게, value는 가방에 넣을 수 있는 보석의 가치이다.

 

해당 문제는 가장 작은 값을 반환해주는 우선순위 큐의 성질을 사용하여 해결해야한다. 

 

• 보석 정보를 무게를 기준으로 내림차순 정렬한다.
• 가방 정보를 내림차순 정렬한다.
• 가방 정보를 순차적으로 확인하면서 가방에 넣을 수 있는 보석의 가치를  -를 붙여서 value에 넣어준다.
• 과정 3을 반복한다.
• 더 이상 넣을 수 있는 보석이 없다면 value의 가장 앞에 있는 값을 가져와 answer에 빼준다.

위의 과정에서 보석의 가치에 -를 붙여주는 이유는 가장 작은 값을 반환하는 우선순위 큐의 성질 때문이다. -를 붙여줌으로써 가장 큰 가치를 가진 보석을 가장 작은 가치를 가진 보석으로 바꿔주고, 가장 작은 값을 반환하는 우선순위 큐가 반환하는 값이 사실은 가장 큰 가치를 가진 보석으로 되게 하기 위해서이다.

 

위의 과정을 코드로 작성하면 다음과 같다.

 

import sys
from queue import PriorityQueue
 
n, k = map(int, sys.stdin.readline().split())
data, bags = [], []
value = PriorityQueue()
answer = 0
 
for _ in range(n):
  data.append(list(map(int,sys.stdin.readline().split())))
 
for _ in range(k):
  bags.append(int(sys.stdin.readline()))
 
bags.sort()
data.sort(key = lambda x : x[0])
 
index = 0
for i in range(k):
  while index < n and bags[i] >= data[index][0]:
    value.put(data[index][1] * (-1))
    index += 1
  if not value.empty():
    answer -= value.get()
print(answer)

 

그리드 유형은 구현 난이도보다는 최적의 해를 찾는 방법을 생각하는 것이 휠씬 더 중요하다고 느끼게 해 준 문제이다.