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

백준 1715 - 카드 정렬하기

문제

코드

import sys
import heapq

input = sys.stdin.readline;

heap = []
N = int(input())
cardSum=0

for _ in range(N):
    card = int(input())
    heapq.heappush(heap, card)

for _ in range(N-1):
    num1=heapq.heappop(heap)
    num2=heapq.heappop(heap)
    cardSum= cardSum+num1+num2
    heapq.heappush(heap, num1+num2)

print(cardSum)

해설

1. 카드를 합치는 횟수는 N-1 번이다.
2. 카드를 합치는데 제일 적은 카드수가 제일 많이 더해져야한다.
3. 따라서 heapq를 이용하여 제일 작은 두수를 pop해서 더해주고 그 더한 값은 다시 heap에 push했다.
4. 카드를 합치는 횟수는 cardSum에 더해주었다.
5. N-1 번이 모두 끝난 후에는 cardSum을 출력해준다.