카드 정렬하기

💻 입력 조건

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

💻 출력 조건

• 첫째 줄에 최소 비교 횟수를 출력한다.

💻 입력 예제

3
10
20
40

💻 출력 예제

100

📖 문제 해결
작은 크기를 가지는 카드 묶음 2개를 선택하여 비교한 후, 그 2개의 카드 묶음을 하나로 합쳐 다시 카드 리스트에 추가하는 과정을 카드가 한 묶음이 될 때까지 반복해나가면 해결할 수 있는 문제입니다.

# n을 입력받기
n = int(input())

# n개의 card 정보를 cards 리스트에 입력받기
cards = []
for i in range(n):
    cards.append(int(input()))

# 총 비교 횟수를 담을 변수 'sum_'을 0으로 초기화
sum_ = 0

while True:
    # 카드 정렬
    cards.sort()
    
    # 가장 작은 크기의 카드 묶음 2개를 골라 합치기
    two_sum = 0
    two_sum = sum(cards[:2])
    
    # 현재까지 비교 횟수 업데이트
    sum_ += two_sum
    
    # 묶은 카드를 cards 리스트에 추가
    cards.append(two_sum)
    
    # 묶는 데 사용된 카드들은 제외
    cards = cards[2:]
    
    # 더 이상 비교할 카드가 없는 경우 반복문 탈출
    if len(cards) == 1:
        break
        
# 비교의 최소 횟수 출력
print(sum_)