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

문제

다음과 같은 규칙으로 카드비교횟수를 카운팅한다할 때 최소 횟수를 구해라.
카드가 3장 {10, 20, 40} 있을 때 비교회수는 다음과 같다.

1. (10 + 20) + (30 + 40) = 100
2. (10 + 40) + (50 + 20) = 120
3. (20 + 40) + (60 + 10) = 130

answer = 100

풀이

카드 각각의 묶음 수는 고유한 값으로 무조건 더해지게 된다.
그렇다면 고른 두 묶음의 합이 최소가 되도록 조건을 만들면 된다.

자세한건 코드에서 살펴보자.

전체코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
q = sorted([int(input()) for _ in range(n)])
answer = 0

# 1. 가장 적은 두 묶음 선택
# 2. 합산 후 결과를 카드리스트에 넣기
while n > 1:
    sum = 0 
    sum += heapq.heappop(q)
    sum += heapq.heappop(q)
    answer += sum
    heapq.heappush(q, sum)
    n -= 1

print(answer)