알고리즘 - Python / 백준 - 1715번 : 카드 정렬하기

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

1715번: 카드 정렬하기

 

---

풀이

• 정렬된 묶음의 카드들을 합쳐 하나의 묶음으로 만들 때 , 가장 적게 비교하도록 만드는 문제이다.
• 문제 자체는 직관적이라 가장 작은 것 2개를 합치고 그걸 다시 배열에 넣고 하는 과정을 계속 진행하면 된다.
• 배열에 넣을 때마다 정렬이 필요하므로 heap을 통해서 위의 알고리즘을 구현하였다.

 

import sys
import heapq
n = int(sys.stdin.readline())
stack = []
for _ in range(n):
    k = int(sys.stdin.readline())
    heapq.heappush(stack, k)
ans = 0
while True:
    if len(stack) == 1:
        break
    a = heapq.heappop(stack)
    b = heapq.heappop(stack)
    ans += (a+b)
    heapq.heappush(stack, a+b)
print(ans)

---