[baekjoon] 백준 1202번(파이썬): 보석 도둑

문제

1202번: 보석 도둑

- 보석점에는 보석이 총 N개 있다.

- 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.

- 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다.

- 가방에는 최대 한 개의 보석만 넣을 수 있다.

- 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 문제이다.

- N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

- 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

- 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

- 모든 숫자는 양의 정수이다.

알고리즘

- 보석의 총 개수와 가방의 개수를 입력받는다.

- 반복문을 통해 보석의 무게와 가격을 입력받는다. 이때, 힙큐를 통해 리스트에 넣는다.

- 각 가방에 담을 수 있는 최대 무게를 입력받는다.

- 무게가 작은 가방부터 보석을 넣기 위해 각 가방에 담을 수 있는 무게를 오름차순으로 정렬한다.

- 반복문을 통해 가방에 담을 수 있는 최대 무게와 보석의 무게를 비교한다.

- 가방에 담을 수 있는 최대 무게보다 작거나 같은 보석이 있는지 확인한다.

- 이때, 작은 보석들은 하나씩 꺼내어 확인한다.

- 작은 보석들 중 제일 비싼 보석을 훔칠 가방에 넣는다.

- 제일 비싼 보석의 가격을 카운트한다.

- 위 과정을 반복한다.

코드

import sys
import heapq

n, k = map(int,sys.stdin.readline().split())
heap = []
for _ in range(n):
    heapq.heappush(heap, list(map(int, sys.stdin.readline().split())))

c = [int(sys.stdin.readline()) for x in range(k)]
# 무게가 작은 가방부터 보석을 넣기위해 오름차순 정렬
c.sort()
# 현재 가방보다 작은 모든 보석들을 넣을 곳
bag = []
# 최대 가격
cnt = 0

for i in c:
    # 가방의 무게보다 작거나 같은 보석이 있는지 확인
    # heap[0][0]보다 크거나 같은 i 사이에 값이 heap 안에 있으면 true
    # 이때, heap[0][0]보다 크거나 같은 i 사이에 값중 heap 안에 있는 값을 하나씩 꺼내어 확인한다.
    while heap and i >= heap[0][0]:
        # 가방에 담을 수 있는 보석중 최대 가격순으로 bag에 넣는다.
        heapq.heappush(bag, -heapq.heappop(heap)[1]) # 최대힙

    # bag에 넣을 수 있는 보석이 있는 경우
    if bag:
        # 최대힙의 부호가 음수이기때문에 -로 연산하여 양수를 만든다.
        # 현재 최대 가격인 보석을 카운트
        cnt -= heapq.heappop(bag)
    # 남은 보석이 없는 경우 끝낸다.
    elif not heap:
        break

print(cnt)

결과

위 코드에서 while문 맨 밑에 print(bag)을 작성하면 가방에 보석을 담는 순서를 다음 출력 화면과 같이 확인할 수 있다.  

<출력화면>

(편의상 무게는 kg, 가격은 원으로 하겠다.) 위 출력 화면을 보게 되면 while문에서 가방에 담을 수 있는 무게보다 작은 보석이 있는지 확인을 하고, 작은 보석이 있다면 하나씩 최대힙을 통해 가방에 담는 것을 확인할 수 있다. 처음에 2kg을 담을 수 있는 가방보다 무게가 작은 보석인 1kg과 2kg이 순서대로 가방에 담기는 것을 볼 수 있다. 무게가 1kg이고 65원인 보석이 가방에 담기고 2kg이고 99원인 보석이 가방이 담긴다. 다 담은 후에는 그중에서 제일 큰 값을 힙팝을 통해 카운트한다. 위 과정을 반복하면 10kg을 담을 수 있는 가방보다 무게가 작은 보석인 5kg이 가방에 담기는 것을 볼 수 있다. 그래서 이전에 있었던 무게가 1kg이고 65원인 보석과 무게가 5kg이고 23원인 보석이 가방에 담기는 것을 볼 수 있다.  이렇게 또 다 담은 후에는 그중에서 제일 큰 값을 힙팝을 통해 카운트한다. 결국 훔칠 수 있는 보석 가격의 합의 최댓값은 164원이 된다. 이때 이전에 담은 보석을 카운트해도 되는 이유는 담을 수 있는 무게가 작은 가방부터 보석을 담았기 때문에 그전에 담을 수 있던 보석을 다음 더 무거운 무게를 담을 수 있는 가방에 담을 수 있기 때문이다.

따라서 코드를 분석하게 되면 가방에 담을 수 있는 무게와 보석의 무게를 비교해서 가방에 담을 수 있는 보석 중 제일 가격이 비싼 보석을 최대힙을 통해 카운트해줘야 한다. 또 while문에 조건을 위 출력 화면을 보면서 잘 이해하면 될 것이다.

github

junjange/CodingTest