[BOJ 1715, Python 3] 카드 정렬하기

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

1715번: 카드 정렬하기

 

풀이

카드묶음이 한 개가 남을 때까지 더하기 때문에 일단 모든 카드의 값은 최소 1번씩은 더해야합니다.

여기서 이제 어떻게 더해야할지가 문제인데, 우리는 최솟값을 구해야하므로 더할 때 과정이 항상 최솟값을 보장 받으려면 최소힙을 이용하여 가장 작은 값을 가진 카드 묶음 2개를 계속 더해주면 됩니다.

 

증명?

만약 카드 묶음이 A, B, C 3개 있는데 A >= B >= C라고 해봅시다.

이때 B + C를 묶고, 이 묶음을 A랑 합치면 A + 2 * B + 2 * C 가 답으로 나옵니다.

B와 C를 먼저 묶지말고,  A와 C를 묶고 B랑 합치면 2 * A + B + 2 * C가 답으로 나옵니다.

두 값을 대소비교를 해본다면 A + B + 2 * C 식에 A를 더하냐, B를 더하냐에 따라 대소가 결정되고, A >= B이므로 A >= B >= C일 때는 B와 C를 합치는 것이 최솟값입니다.

A+B도 마찬가지로 B+C와 비교하면 적어도 n = 3일 때는 B+C를 더하는 것이 최솟값임을 알 수 있습니다.

 

이걸 이제 카드 묶음이 n개가 될 때를 확인해봅시다.

카드 묶음 n개에서 무작위로 3개를 뽑아보면 A >= B >= C가 성립하는 카드 묶음 3개가 뽑힐 것 입니다.

윗 문단에서 n = 3일 때 최솟값 구하는 방법을 증명을 했으니 n개의 카드 묶음에서 카드묶음 3개를 어떤 방식으로 뽑아도 A >= B >= C가 되는 카드묶음 3개가 나옴이 보장되므로 B와 C를 더하는 것이 무조건 최솟값을 보장합니다.

그러므로 최소힙을 이용하여 가장 작은 값 두 개를 더하는 것이 최적해입니다.

 

코드

from heapq import *
arr = []
for i in range(int(input())):
    heappush(arr, int(input()))
ans = 0
while len(arr) != 1:
    x = heappop(arr)
    y = heappop(arr)
    ans += x + y
    heappush(arr, x + y)
print(ans)