[BOJ] 1202번 : 보석 도둑(정렬, 우선순위 큐, 그리디)

접근

보석 도둑이라 그래서 DP 문제일 줄 알았지만, 그리디 형태로 접근하는 문제였다. 아. 그리디 너무 싫다. 너무 어렵다. 문제 자체는 간단한데 풀이방법에서 이게 맞을까? 하면 이게 맞는 그런 문제들이다 항상..

처음 접근은 수집하지 않은 보석을 저장해두기 위해, heap트리 두개를 사용해서 접근했는데 시간초과가 났다. 분명 접근은 맞는 것 같은데, 시간 초과를 해결할 수가 없어서, 질문 게시판을 찾아보며 다른 사람들은 어떻게 구현했는지 보고 구조를 참고하여 해결했다.

 

해결

그리디 문제는 욕심쟁이기 때문에, 문제에 정렬이나, 우선순위 큐(힙 트리 등) 구조를 활용하여 조건이 되는 애들 중에 가장 큰 값을 챙기려고 하는 의도가 담겨있다. 그 의도를 생각하며, 아래 해결을 참고해보자.

 

• 먼저  보석과 가방의 수용량을 모두 입력 받은 뒤, 보석의 무게, 가방의 수용량에 대해 오름차순으로 정렬을 시행해준다.
• 가방의 수용량의 순회를 진행하며, 작은 수용량 부터 담을 수 있는 보석을 탐색한다.
• 담을 수 있는 보석은 외부 리스트에 저장해둔다. => 저장할 때 우선순위 큐를 이용해서, 가장 큰 가치를 갖는 보석을 찾을 수 있도록 구성하자
• 위에서 담은 보석은 보석 리스트에서 제거한다.
• 담을 수 있는 보석 탐색이 끝나면, 담을 수 있는 보석이 있다면 가장 큰 값을 뽑아서 전체 가치에 더해준다.

위의 과정 중 볼드체로 작성한 내용에 대해 고민해보자.

순회 중에 빈 리스트를 만들어, 현재 가방의 수용량보다 작은 무게의 보석들을 탐색할 수도 있다.
그렇게 된다면, 매번 전체 보석을 비효율적으로 탐색하는 과정이 필요할 것이다.
반면에, 우리는 가방 수용량과 보석의 무게에 대해 오름차순으로 정렬을 수행했기 때문에, 앞서 탐색한 가방의 수용량은 뒤에 탐색할 가방의 수용량보다 작음이 보장된다. 그렇기에 외부 리스트에 앞서 탐색한 가방의 수용량에 맞는 보석을 외부 리스트에 저장해두고, 전체 보석에서 해당 보석을 제거하면, 후에 탐색할 보석의 갯수도 줄고, 뒤에 탐색할 가방의 수용량에 대해서는 저장해둔 외부 리스트에서 우선순위 큐를 이용해서 찾아낼 수 있다.
이로써 더 효율적인 탐색이 가능해진다.

 

그리디 문제는 해결과정에서 어떻게 가장 큰 값을 효율적으로 넣을지 고민하는게 가장 큰 문제인 것 같다.

많이 풀어봐야지 알 수 있을 듯..

 

코드

import heapq, sys

input = sys.stdin.readline

N, K = map(int, input().split())
gems = []
for _ in range(N):
    m, v = map(int, input().split())
    gems.append((m, v))
    
C = []
for _ in range(K):
    C.append(int(input()))
C.sort()
gems.sort()

total = 0
tmp = []
for capable in C:
    while gems and gems[0][0] <= capable:
        heapq.heappush(tmp, (-gems[0][1], gems[0][0]))
        heapq.heappop(gems)
    
    if tmp:
        total += -heapq.heappop(tmp)[0]
        
print(total)