문제

링크

풀이

Knapsack 문제로 접근하였으나 아니였다. 가방이 여러개가 있으며 가방 하나에는 딱 하나의 보석만 담을 수 있다는 조건이 있다. 따라서 최대한 비싼 보석을 하나라도 더 훔치는 것이 중요하다.

비싼 보석인데 무겁다고 해서 더 싸고 가벼운 보석에게 가방을 양보하게 되면 훔칠 수 있는 보석의 가격이 작아지므로 이는 의미없는 행동이 된다. 포인트는 최대한 비싼 보석부터 최대한 작은 가방에 담는 것이다!
전체적인 로직은 아래와 같다.

1. 가방에 담을 수 있는 최대 무게를 기준으로 오름차순 정렬한다.

2. 보석의 무게 <= 가방의 무게이면 가방에 담아서 훔친다. 단, 보석의 무게 <= 가방의 무게인 보석들 중에 가격이 가장 비싼 보석 하나를 훔쳐야한다.

3. 모든 가방과 모든 보석에 대해 위 과정을 반복한다.

처음 구현할 때 보석의 무게를 기준으로 내림차순 정렬, 가방에 담을 수 있는 최대 무게를 기준으로 오름차순 정렬한 후 보석을 가방에 담을 수 있다면 바로 훔쳤고, 방문 배열을 통해 방문처리를 해주었다. 하지만, 시간초과가 발생하였다. 이렇게 풀면 O(NK) 시간복잡도가 나온다. 300,000 x 300,000 = 90,000,000,000로 당연히 시간초과가 나게된다.

해답 포인트는 우선순위 큐 [O(NlogN)] (시간복잡도를 낮춰야하기 때문에 사용함!)를 사용하는 것이다. 우선순위 큐를 사용해 가방에 담을 수 있는 보석을 탐색할 때 최소힙으로 구현한 우선순위 큐를 사용한다. 가방에 담을 수 있는 보석들 중 가장 비싼 보석을 훔칠 때 최대힙으로 구현한 우선순위 큐를 사용한다. 여기서 최소힙은 오름차순 이진트리, 최대힙은 내림차순 이진트리라는 것만 알고 넘어가자. 추후에 자세히 설명할 예정이다.

※ Python에서 힙은 최소힙으로 구성되어 있다. 따라서 최대힙으로 구현한 우선순위 큐를 사용하려면 원소의 부호를 임시로 변경하는 방식을 사용하면 된다. (-부호 붙이는 방식)

코드

import sys
import heapq

input = sys.stdin.readline
N, K = map(int, input().split())
jewels = []
for _ in range(N):
    heapq.heappush(jewels, list(map(int, input().split())))

backpacks = []
for _ in range(K):
    backpacks.append(int(input()))
backpacks = sorted(backpacks)

ans = 0
possible = []
for backpack in backpacks:
    while jewels and backpack >= jewels[0][0]:
        heapq.heappush(possible, -heapq.heappop(jewels)[1])
    if possible:
        ans -= heapq.heappop(possible)

print(ans)

시간초과 코드 (정답 X)

# Python3 / PyPy3 모두 시간 초과
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
jewels = []
for _ in range(N):
    x, y = map(int, input().split())
    jewels.append((x, y))
jewels = sorted(jewels, key=lambda x: -x[1])
visited_jewels = [False] * N

backpacks = []
for _ in range(K):
    backpacks.append(int(input()))
backpacks = sorted(backpacks)
visited_backpacks = [False] * K

ans = 0
for i in range(len(backpacks)):
    for k in range(len(jewels)):
        if jewels[k][0] <= backpacks[i] and not visited_backpacks[i] and not visited_jewels[k]:
            ans += jewels[k][1]
            visited_jewels[k] = True
            visited_backpacks[i] = True

print(ans)