소스코드
import sys
import heapq
input = sys.stdin.readline
N = int(input().strip())
cards = [int(input().strip()) for _ in range(N)]
heapq.heapify(cards)
result = 0 # 결과 : 총 누적합
# 최소힙에서 2개씩 꺼내서 합산 후 다시 힙에 추가 -> 반복
while len(cards) >= 2:
num_first = heapq.heappop(cards)
num_second = heapq.heappop(cards)
sum_result = (num_first + num_second)
# 힙에 합산 결과를 넣고 결과를 누적
heapq.heappush(cards, sum_result)
result += sum_result
print(result)
Python
복사
풀이
•
예제 입력에는 10,20,40이 있습니다.
◦
수식을 어떻게 사용하면 가장 적은 누적합산을 만들어낼 수 있을까요? 여러 예시를 생각해보면서 체크해보시면 자연스레 찾는 한 가지가 있습니다. “매번 가장 작은 값 두 가지를 합산해서 결과를 도출하면 된다”입니다.
◦
계속 작은 값 두 가지를 찾아내야하고, 합산을 다시 넣어 최소값을 빠르게 찾도록 정렬하려면 최소힙이 가장 좋겠다는 생각을 했습니다.
•
힙을 떠올리는 과정이 조금 어려울 수 있지만, 힙을 떠올리고 나면 나머지 과정은 골드 문제인가 싶을만큼 쉽습니다. 2개씩 꺼내서 값을 합산하고, 이를 누적한 후, 다시 최소힙에 합산 결과를 넣어줍니다.
◦
이걸 힙의 개수가 2개 이상일 때까지 확인하면 됩니다 : 4개의 경우도 무조건 마지막 값 두 개가 남으며, 홀수 개의 경우에도 2개가 합산되고 하나를 힙에 추가하다보면 마지막엔 2개가 남습니다. 아마 마지막 연산이 끝나 결과에 누적하고 나면 힙에는 하나가 남아있을 겁니다(더 이상 사용 안 하는).
•
결과를 출력하면 끝!!