문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력

3
10
20
40

예제 출력 1

100

✅ 나의 코드

from sys import stdin as s
import heapq

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline().strip())

# 가장 작은 카드 부터 2개씩 꺼내올 예정. -> heap 정렬하고 minheap을 꺼내오자.
cards = []
for i in range(n):
    heapq.heappush(cards, int(s.readline()))

# result에 minheap 2개의 합을 누적해갈 것.
result = 0

# n-1번째 마지막에 heappush한 카드더미는 합산하지 않으므로 범위도 n-1까지만 지정
for i in range(n - 1):
    # 카드 더미 2개를 꺼낸다. (minheap)
    first_card = heapq.heappop(cards)
    second_card = heapq.heappop(cards)
    # 2개를 더해서
    sum_val = first_card + second_card
    # result에 누적하고
    result += sum_val
    # 합계는 다시 cards에 heappush
    heapq.heappush(cards, sum_val)

print(result)

처음에 문제를 제대로 이해 못해서, 오름차순 정렬하고 맨 앞의 카드랑 더하는 걸 반복하는 문제인 줄 알았다. 당연히 fail!

💩 처음에 제출했던 실패 코드

from sys import stdin as s
from collections import deque

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline().strip())

cards = []
for i in range(n):
    cards.append((int(s.readline())))

cards.sort()

result = cards[0]
sum = cards[0]

for i in range(1, n):
    result += cards[i]
    if i == n - 1:
        break
    sum += cards[i]
    result += sum

print(result)

질문 게시판의 반례들을 살펴봐도 처음에는 왜 그런 결과들이 나오는지 이해를 잘 못하겠어서, 문제 이해를 위해 이코테를 슬쩍 봤다. heapq를 사용하는 문제? 아.. (깊은 깨달음) 최소 카드 더미 2개의 합산 값이 반드시 남은 카드 더미 중 가장 작은 값보다 작을 것이라는 보장이 없구나. 심지어 남은 카드 더미들과 비교해도 가장 큰 값일 수도 있다. 그래서 heap에 때려 넣으면 알아서 minheap을 뽑아주는 효자 heapq라이브러리를 이용해야 하는거군.

여기까지 이해하고 코드를 작성해보니 어렵지 않았는데, 처음에는 for문의 범위를 지정하는 게 어려웠다. n까지로 범위를 지정하니 second_card = heapq.heappop(cards) IndexError: index out of range 에러가 났다.

결론적으로는 n - 1까지로 범위를 지정하면 된다. 이유는 한 번 순회할 때마다 카드를 2개씩 heappop하고 1개를 heappush하니까 카드 배열에서 1개씩 줄어드는 셈이다. 마지막에 남은 카드 2개를 더하고 합계를 heappush하는데, 그럼 마지막에는 cards 배열에 카드더미가 1개만 남는다. 이미 result에 카드 더미가 다 모여 있기 때문에 cards 배열에 있는 마지막 하나는 무시해야 한다. 그래서 n - 1까지로 범위를 지정하는 것이다.

그리고 heappush 쓸 때 자꾸 배열을 인자로 같이 전달하는 걸 까먹어서 오류가 난다 ㅋㅋㅋ 이제 안 까먹기로 다짐! 화이팅!!