[BOJ 1202] 보석 도둑 (Python)

kimdukbae·2021년 4월 8일
0

문제

링크



풀이

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)
profile
A Student of Computer Science

0개의 댓글