[백준/python] 1715번: 카드 정렬하기

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

 

문제 코드

from heapq import heappush, heappop
hq=[]
n=int(input())
for _ in range(n):
    x=int(input())
    heappush(hq, x)
#마지막에 합쳐지는수는 어차피 동일
#대신 초반부터 적게 합치고 합쳐야함.
ans=0
while(len(hq) !=1):
    a = heappop(hq)
    b = heappop(hq)
    ans += a+b
    heappush(hq, a+b)

print(ans)

코드 설명

계속 합치면서 더하기 때문에 가장 적은 수끼리 더하고를 반복해야 합니다. 이때 이미 합한 값도 포함하여 가장 작은 두 개를 합쳐야하니 합한값을 다시 힙에 넣어줬습니다. hq의 길이가 1이될때까지 반복한 후 답을 출력합니다.