1. 우선 스택을 이용해서 차례대로 더해보자.

import sys
input = sys.stadin.readline
N = int(input())
cards = list(int(input()) for _ in range(N))
tmp = cards[0]
stack_list = []
for i in range(1, N):
    tmp = tmp+cards[i]
    stack_list.append(tmp)
print(sum(stack_list))

8%에서 틀렸다. 아무래도 답이 아닌 것 같다.

반례를 보니 30,40,50,60이 있을 때 최소 비교는 360이다.

이 코드는 370을 뱉는다.

이유를 알겠다.

-> 최솟값을 구해서 더해야 하는데, 그냥 무지성으로 앞에서부터 더하다 보면 최솟값이 아닌 값을 더할 수 있게 됨

2. 최소값을 힙큐를 이용해 2개 뽑아낸 후, 더한 값을 다시 안 쪽에 집어넣고 더한 값은 스택에 계속 더한다. 알고리즘에 하나 남을 때까지 반복한다.

import heapq
import sys
sys.stdin = open('input.txt')

N = int(input())
answer = 0
# 갯수가 하나밖에 없는 카드 뭉치는 그냥 반환
if N == 1:
    print(int(input()))
else:
	# 카드 뭉치를 리스트로 받아줌(사실 빈 리스트 생성 후 힙푸시로 넣어도 무방함. 그게 더 빠를 듯)
    cards = list(int(input()) for _ in range(N))
    # 리스트를 힙큐로 만들어 줌
    heapq.heapify(cards)
    while len(cards)>1:
    	# heappop을 이용해 최솟값을 2개씩 뽑아준다.
        stack1 = heapq.heappop(cards)
        stack2 = heapq.heappop(cards)
        # 더한 값을 일단 answer에 담아주고
        answer += (stack1+stack2)
        # heappush를 이용해 다시 힙큐 속으로 넣어준다.
        heapq.heappush(cards, stack1+stack2)
    print(answer)

틀렸다.

100%에서

왜냐하면 정답은 '비교횟수'이기 때문에 하나만 있으면 비교횟수가 0이어야 하는데 예외 처리를 받아오는 카드 뭉치 숫자로 했다.(빠간가)

3. 오류 수정

import heapq
import sys
sys.stdin = open('input.txt')

N = int(input())
answer = 0
if N == 1:
    print(0)
else:
    cards = list(int(input()) for _ in range(N))
    heapq.heapify(cards)
    while len(cards)>1:
        stack1 = heapq.heappop(cards)
        stack2 = heapq.heappop(cards)
        answer += (stack1+stack2)
        heapq.heappush(cards, stack1+stack2)
    print(answer)

정답!

1. '리스트 안'에서 최솟값을 구하는 건 무조건 힙큐 생각해봅시다.

2. 조건을 '제대로' 보고 제발 문제를 풉시다.

3. 힙큐는 무적이다 파이썬은 신이고