[알고리즘] 백준1715 카드정렬하기

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

정렬이 되어있는 상태에서 최소값이 구해질 수 있으므로, 힙 정렬을 사용하는 우선순위큐를 heapq 모듈을 이용해 구현한다.

먼저 내가 시도했던 방법이다.

import sys
import heapq

N = int(sys.stdin.readline())

priority_queue = [] # 입력으로 들어온 카드를 내림차순 정렬해주는 우선순위 큐
cal_queue = [] # 입력 카드가 두 묶음이 생길때마다 값을 꺼내 합을 구하고, 다시 저장하는 계산용 큐

# 우선순위 큐 초기화
for _ in range(N):
    heapq.heappush(priority_queue, int(sys.stdin.readline()))

sum = 0
while True:
	# 계산용 큐에 두 묶음이 들어있다면, 두 묶음의 합을 구함
    if len(cal_queue) // 2 == 1:
        temp = 0
        while cal_queue:
            temp += heapq.heappop(cal_queue)
           
        # 이후 그 합을 다시 계산용 큐에 저장함
        heapq.heappush(cal_queue, temp)
        sum += temp
        
        # 더 이상 추가할 값이 없을 경우 while문 종료
        if not priority_queue:
            break
    else:
    	# 계산용 큐에 두 묶음이 없다면, 계산용 큐에 숫자 추가
        heapq.heappush(cal_queue, heapq.heappop(priority_queue))
print(sum)

이렇게 구하면 본문에 나오는 예제 같은 경우 원하는 답이 출력된다. 그러나 막상 제출을 시도하면 오답이라는 결과가 나왔기 때문에, 반례를 찾아보게 되었다.
위 코드에 입력으로

4
30
40
50
60

을 넣어주게 되면 370이라는 답이 나온다. 그러나 이는 오답이다. 이 테스트 케이스의 경우 답은 360이 되어야한다.

그렇다면 왜 오답일까?

문제를 잘못이해하고 구현한 탓이었다. 현재 내 코드의 경우 30 40 50 60의 최솟값을 구하는 과정은 다음과 같다.

30 + 40 = 70 -> sum = 70
70 + 50 = 120 -> sum = 70 + 120 = 190
120 + 60 = 180 -> sum = 190 + 180 = 370
그러나 위의 케이스의 경우 30부터 60까지 순차적으로 더하는 내 코드의 경우가 아니라,

30 + 40 = 70 -> sum -> 70
50 + 60 = 110 -> sum -> 70 + 110 = 180
70 + 110 = 180 -> sum -> 180 + 180 = 360
과 같이 되어야 한다는 것이다.

내 코드가 틀린 원인은 본래 입력을 받은 우선순위 큐에 추가로 계산을 위한 큐를 하나 더 추가했기 때문에, 오차가 발생하게 되었다. 다음은 이를 개선하기 위해서 입력 받은 큐를 재활용하여 답을 도출하는 코드이다.

import sys
import heapq

N = int(sys.stdin.readline())

priority_queue = []
# 우선순위 큐 초기화
for _ in range(N):
    heapq.heappush(priority_queue, int(sys.stdin.readline()))

sum = 0

# 마지막에 heappush()를 수행해주기 때문에, 큐의 크기가 0이 아닌 1이하 일때 종료하도록 한다.
while len(priority_queue) > 1:
	# 두 묶음씩 뽑아서 더한다
    temp = heapq.heappop(priority_queue) + heapq.heappop(priority_queue)
    sum += temp
    # 더한 값을 다시 큐에 넣어줌
    heapq.heappush(priority_queue, temp)

print(sum)