[백준] 1715 카드 정렬하기(Python)

백준 - 1715 카드 정렬하기

풀이

1. 카드 묶음이 오름차순으로 정렬되어 있어야 비교를 최소한으로 할 수 있음
   -> heapq를 사용해서 오름차순으로 저장

2. 묶음이 한 개이면 비교할 필요 없음 -> print(0)

3. 한 개 이상이면 앞에서 두 개씩(num1, num2) 뺀 다음 두 수를 더한 값을 answer에 저장하고 heap에 저장
   ex) heap = [10, 20, 40] 인 경우
   answer = 10 + 20
   heap = [30(=10+20), 40]
   ...

삽질

처음에는 3번 풀이로 하지 않고, answer에 직접 계산을 해줬음
heap = [10, 20, 40]인 경우
총 더하는 값 = (10 + 20) + ((10 + 20) + 40) 임을 이용해서 해결하고자 했다...

...

else:
    answer = 0
    n = 0
    while heap:
        answer = answer * n + heappop(heap)
        n += 1
    print(answer)

답은 나오는데 백준에서는 출력초과로 틀렸다고 했다
왜일까...........
결국 heap을 heap답게 푸는 방식으로 해결..

코드

from heapq import heappush, heappop
from sys import stdin

heap = []

for i in range(int(stdin.readline())):
    heappush(heap, int(stdin.readline()))

if len(heap) == 1:
    print(0)
else:
    answer = 0
    while len(heap) > 1:
        sum = heappop(heap) + heappop(heap)
        answer += sum
        heappush(heap, sum)
    print(answer)