[python] 백준 1202번 : 보석 도둑 (정렬, heapq)

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

1202번: 보석 도둑

 

 

1. 정답 코드 

import heapq
from collections import deque

# 보석의 개수, 가방의 개수
n, k = map(int, input().split())
jewel = []
for _ in range(n):
    # 보석의 무게, 보석의 가격
    m, v = map(int, input().split())
    jewel.append([m, v])
# 가방에 담을 수 있는 최대 무게
c = sorted([int(input()) for _ in range(k)])
jewel.sort(key=lambda x:(x[0], -x[1]))
result = 0
heap = []
# 큐에서 제일 작은 값 제거할 수 있는 방법(?)
for i in range(k):
    while jewel and c[i] >= jewel[0][0]:
        heapq.heappush(heap, -jewel[0][1])
        heapq.heappop(jewel)
    if heap:
        result += heapq.heappop(heap)
    if not heap and not jewel:
        break

print(-result)

 

2. 틀린 코드

import heapq
from collections import deque
import sys
sys.stdin = open('1202.txt', 'r')
# 보석의 개수, 가방의 개수
n, k = map(int, input().split())
jewel = []
for _ in range(n):
    # 보석의 무게, 보석의 가격
    m, v = map(int, input().split())
    jewel.append([m, v])
# 가방에 담을 수 있는 최대 무게
c = sorted([int(input()) for _ in range(k)])
jewel.sort(key=lambda x:(x[0], -x[1]))
result = 0
deq = deque(jewel)
heap = []
# 가방에 담을 수 있는 보석을 찾아보자
for i in range(k):
    while deq:
        # 가방이 담을 수 없는 보석이 등장했다면
        if heap and c[i] < deq[0][0]:
            result += (-heapq.heappop(heap))
            break
        # 가방이 담을 수 있는 보석인 경우
        m, v = deq.popleft()
        heapq.heappush(heap, -v)

print(result)

반례) 아래와 같은 testcase를 대입하면 아래와 같이 값이 들어온다. 가방의 무게가 15일 때 result에는 [8, 55]의 가격 55가 들어와야 한다. 하지만 if heap and c[i] < deq[0][0]: 가 동작하지 않으므로 heap에서 원소를 꺼낼 수 없다.

9 5
4 5
4 9
4 10
8 55
14 20
9 15
8 55
8 5
11 54
10
5
4
15
20