1715 파이썬 카드 정렬하기

카드 정렬하기 !!

첫 시도:

가능한 순열 조합을 모두 계산하고 최솟값을 찾으려고 했으나 

ㅋㅋㅋ

이 문제는 숨겨진 규칙이 있었으니.. 바로 가장 작은 카드 수 부터 더해가야 한다는 것이다.

그래서 heap 자료 구조를 이용하여 카드 들 중에서 카드 수가 작은 것을 빼내어 더하고, 이 더한값을 다시 heap에 넣어줘서 다시 더해지도록 한다 

 

heapq 라이브러리 오랜만에 쓰는데 이 참에 파이썬 힙 자료구조 라이브러러 쓰는 방법도 확실하게 숙지해야겠따. 

import heapq

n = int(input())
heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap,data)

result = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap) # 카드 더미 두개씩 더해 나가야 하니까
    temp_sum = one + two
    result += temp_sum
    heapq.heappush(heap, temp_sum)
print(result)