알고리즘 유형 : 정렬, 우선순위 큐
풀이 참고 없이 스스로 풀었나요? : X

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

소스코드 (파이썬)

import sys, heapq
scan = sys.stdin.readline

N, K = map(int, scan().strip().split())

jewels = []

for _ in range(N):
    M, V = map(int, scan().strip().split())
    jewels.append((M, V))

# 보석 무게가 가벼운 것부터 pop해서 쓰기 위해 무게 기준 내림차순 정렬
jewels.sort(reverse=True, key=lambda x:x[0])

bags = []

for _ in range(K):
    C = int(scan().strip())
    bags.append(C)

# 가방 무게가 가벼운 것부터 pop해서 쓰기 위해 무게 기준 내림차순 정렬
bags.sort(reverse=True)

# 현재 단계의 가방에 넣을 수 있는 보석 후보군들 (가격 기준 우선순위 큐)
jewel_candidate = []

# 결과값
V_sum_max = 0

# 모든 가방에 보석 넣기 시도
while bags:
    # 남아있는 가용 가방 중 최소 용량 가방
    bag_weight = bags.pop()

    # 남아있는 모든 보석들에 대해, 가방에 넣을 수 있는 후보군인지 판별
    while jewels:
        jewel = jewels.pop()
        M, V = jewel

        if M <= bag_weight:
            heapq.heappush(jewel_candidate, -V)
        else:
            jewels.append(jewel)
            break
    
    if jewel_candidate:
        V_sum_max += -heapq.heappop(jewel_candidate)

print(V_sum_max)

핵심 아이디어

1. 가방 무게 작은 것부터 작업
2. 보석 후보군을 우선순위 큐에 넣고 빼기

풀이 요약

1. 가방을 무게 기준 내림차순 정렬한다. (가방 무게가 작은 것부터 pop해서 쓰기 위함)

   • 가방을 무게가 작은 것부터 꺼내 쓰려는 이유는, 만약 무게가 3, 7인 보석이 있고, 무게가 10, 3인 가방이 있다고 하자. 이 때 무게가 10인 가방부터 써서 3인 보석을 담으면, 무게가 3인 가방에 무게가 7인 보석을 담을 수 없다. 이런 경우 때문에, 무게가 작은 가방부터 고려하는 것이다.

2. 보석을 가벼운 것부터 pop해서 후보 판별을 해주기 위해 무게 기준 내림차순 정렬해둔다.

3. 모든 가방을 순회한다. 각 가방에 대해 다음을 수행한다.

   • 남아있는 모든 보석들에 대해, 현재 가방에 넣을 수 있는 보석 후보를 모두 우선순위 큐에 넣어준다. (이 때, 전 단계의 가방에 대한 후보군을 큐에 넣어뒀다면, 이 후보는 현재 가방에서도 유효하다. 왜냐면 현재 가방은 이전 가방보다 용량이 더 크기 때문)
   • 무게를 초과하는 보석이 등장하거나, 모든 보석을 다 돌고나면 "모든 보석 순회"를 벗어난다.
   • 우선순위 큐에 보석 후보가 존재한다면, 해당 보석을 해당 가방에 넣는다(=결과 변수에 보석 가격을 더한다.)

4. 모든 가방을 순회하고나면, 결과 변수에 있는 값을 결과값으로 취한다.

어려웠던 점, 배운 점

처음에 가방을 무게 기준 오름차순 정렬하고, 보석을 가치 내림차순, 무게 오름차순 정렬해준 뒤, 가방을 무게가 작은 것부터 하나씩 순회하면서, 모든 보석을 대상으로 가치가 높은 것부터 순회하며 같은 가치일 경우 낮은 무게를 우선으로 탐색하여 가방에 넣도록 하였다. 이렇게 하니 시간초과가 났다.

이 문제의 핵심은 가방을 가벼운 것부터 고려하는 점과, 현재 순회 단계의 가방에 대해, 보석 후보군을 우선순위 큐에 모두 넣은 후, 구한 후보에서 우선순위가 가장 높은 (가격이 가장 높은) 것을 뽑아서 가방에 넣는 것이다.

우선순위 큐 아이디어를 떠올리지 못해서 시간 초과가 났다. 나는 특정 가방에 넣을 보석을 판별할 때, 매번 모든 보석을 대상으로 순차적으로 탐색했는데 이걸 우선순위가 가장 높은 보석을 뽑아야하는 상황을 파악하여 우선순위 큐 활용을 떠올리는 능력이 중요한듯하다. 앞으로 유사한 문제가 나오면 이런 아이디어를 떠올릴 수 있게 유의해야겠다.