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

📖 문제

1715번: 카드 정렬하기

 

🔎 풀이

그리디하게 해결할 수 있는 문제입니다. 새로 만들어진 묶음은 또다른 묶음과 다시 비교를 진행해야합니다. 그러므로 가장 작은 두 묶음을 골라 새로운 묶음을 만들어내는 것이 유리합니다. 파이썬의 heapq를 활용하면 간단하게 구현이 가능합니다.

 

💻 코드

import sys
import heapq
input = sys.stdin.readline

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

for i in range(N-1):
    # 가장 작은 두 묶음 꺼내기
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    k = a + b
    # 결과 저장
    result.append(k)
    heapq.heappush(heap, k)
   
print(sum(result))