[백준] 1202 - 보석도둑 (G2)

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

1202번: 보석 도둑

자료구조를 사용하는 그리디 문제이다.

우선해야하는 조건이 2개가 엮여 있어서 난이도가 있는 문제였다.

 

나는 그리디 알고리즘 강의를 다시 복습해서 보고나서 아래와 같은 사고로 문제를 풀었다.

결국 그리디도 최적해를 구하는 알고리즘 중 하나인데,

이 문제에서 구해야하는 것은 '보석 가치 합의 최대'이다.

그렇다면 일단 보석의 가치만 놓고보면, 보석의 가치가 큰 것을 골라야한다.

 

그리고 가방의 경우를 보면, 가방하나에는 어차피 하나의 보석밖에 넣지 못하는 상황이다.

이 때 무게가 여유있는 가방에는 무거운 보석, 가벼운 보석 모두를 넣을 수 있고,

무게에 여유가 없는 가방에는 가벼운 보석만을 넣을 수 있다.

따라서 제한조건이 많은 무게가 여유 없는 가방부터 채워나가야 이득이다.

 

무게에 여유가 많은 가방에 가벼운 보석을 넣는 경우가 최적해라면,

무게에 여유가 없는 가방에 가벼운 보석을 넣는 경우가 해당 최적해를 포함하기 때문에,

무게에 여유 없는 가방에 가벼운 보석을 넣는 것이 더 이득이다.

 

이 둘을 조합하면 아래와 같은 과정으로 답을 구할 수 있다.

 

1. 무게에 여유가 없는 가방부터 채우되,

2. 해당 가방에 넣을 수 있는 보석 중 가장 가치가 큰 보석을 담는다.

3. 다음 가방에 넣을 수 있는 보석을 기존에 담고 남은 넣을 수 있는 보석에 추가한다.

4. 다시 넣을 수 있는 보석 중 가치가 가장 큰 보석을 담는다.

5. 모든 가방에 대해 반복한다.

 

이때 중간에 '넣을 수 있는 보석들'을 갱신하면서 가치가 가장 큰 보석을 뽑으려면

'우선순위큐' 자료구조를 사용해야한다.

 

import sys, heapq
input = sys.stdin.readline
n, k = map(int, input().split())
jewel, bags = [], []
for _ in range(n):
    jewel.append(tuple(map(int, input().split())))

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

bags.sort()
jewel.sort(reverse=True)

answer = 0
pq = []
for bag in bags:
    while jewel and jewel[-1][0] <= bag:
        m, v = jewel.pop()
        heapq.heappush(pq, (-v, m))
    if pq:
        answer += (-heapq.heappop(pq)[0])

print(answer)

 

이때 문제 조건에서 놓치기 쉬운 코너케이스가 '가방의 개수'가 '보석의 개수'보다 많은 경우이다.

보석이 가방보다 적게 있다면 빈가방이 생길 수 있다는 코너케이스를 잘 처리하면  AC를 받을 수 있다.