1715 카드 정렬하기 _python

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

문제를 이해하는데만 1시간이 넘게 걸렸다. 잘못 생각해서 고생좀 했다..ㅜㅜ

 

예제에서 10 20 40을 입력받으면 (10+20) +  (10+20+40) 으로 100이 나온다.

추가 예시로 올려준것도 찾아봤다.

https://www.acmicpc.net/board/view/72799

30 40 50 100이 입력으로 주어진다.

처음엔 순서대로 더하면 되는줄 알고 (30+40) + (30+40+50) + (30+40+50+100)을 하면 410이 나온다.

 

이방식을 구현하려고 힙을 사용했다.

최소힙을 구현을 했고, 최소힙에 값을 2개 꺼내서 ans에 추가를 해주고, 더한 값을 다시 힙에 넣어준다.

그러면 10 11 12 13 같이 입력을 받는경우도 쉽게 해결이 된다.

최소값부터 순서대로 더한다면 10+11을 하고 21+12, 34+13 순으로 되지만 

이런 계산방법 보단 10+11, 12+13 -> 21+25 가 더 적기떄문이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import heapq
import sys
input = sys.stdin.readline

"""

"""

N = int(input())
heap = []

for _ in range(N):
    heapq.heappush(heap, int(input()))

ans = 0
while len(heap)>1:
    x = heapq.heappop(heap)
    y = heapq.heappop(heap)
    ans += x + y
    heapq.heappush(heap, x + y)

print(ans)