1️⃣ 문제 설명

3️⃣ 1트 - DP로 풀기

정렬이 된 배열이라고 가정합시다.

1. 카드 묶음이 [10, 20, 30]일 때
   최소 비교 횟수 = (10+20) + (10+20+30)

2. 카드 묶음이 [10, 20, 30, 40]일 때
   최소 비교 횟수 = (10+20) + (10+20+30) + (10+20+30+40)

라고 생각하고 DP로 문제 풀기를 츄라이 해봤습니다.

import sys

input = sys.stdin.readline

n = int(input())

cards = []
for _ in range(n):
    cards.append(int(input()))

# 리스트 정렬
cards.sort()

dp = []

# 첫 번째 원소 삽입
dp.append(cards[0])

for i in range(n-1):
    dp.append(dp[i] + cards[i+1])

cnt = 0
for i in range(1, n):
    cnt += dp[i]

print(cnt)

이렇게 쉽게 풀리면 백준이 아니죠

4️⃣ 2트 - 우선순위 큐

그리고 질문 게시판을 참고하여 반례를 찾을 수 있었습니다.

카드 묶음이 [10, 10, 10, 10]일 때 1번째 방법으로 하면 140이 나온다.
이를 통해 제 로직이 잘못된 것을 알 수 있었습니다.

그리고 문제 아래 알고리즘 분류를 슬쩍 봤습니다.

우선순위 큐를 쓰면 따로 정렬을 해줄 필요가 없겠구나 !!

그리고 [10, 10, 10, 10], [10, 10, 10, 10, 10], [10, 20, 30, 40]일 때 3가지 경우를 예로 카드 정렬 과정을 그림으로 그려보았습니다.

그림을 그리면서

• 가장 작은 수 두 개를 더해서 나온 수를 다음 배열에 저장을 하는구나
• 가장 작은 수 두 개를 더해서 나온 수들을 더한 값이 최종적인 최소 비교 횟수구나
• 마지막에는 수가 하나만 남는구나

라는 것을 깨달을 수 있었습니다.

이제 다시 구현해봅시다

import sys
from queue import PriorityQueue

input = sys.stdin.readline

n = int(input())

q = PriorityQueue() # 우선순위 큐
count = 0 # 최소 비교 횟수를 담을 변수

for _ in range(n):
    q.put(int(input()))

# 우선순위 큐에 원소가 하나만 남을 때까지
while q.qsize() != 1:
    temp = q.get() + q.get() # 가장 작은 두 수를 더해서
    count += temp # count에 더해주고
    q.put(temp) # 더한 값을 다시 우선순위 큐에 넣어준다

print(count)

5️⃣ 3트 - Heap

이 글(독수리 아님)을 참고해서 PriorityQueue를 사용하면 시간 초과가 발생하는 경우가 종종 있기 때문에, 그럴 때는 힙을 사용해보라는 조언을 얻을 수 있었습니다.

PriorityQueue는 heapq를 사용하여 구현됩니다.
PriorityQueue는 Thread-safe하고, heapq는 Non-safe합니다.
Thread-safe하기 위해서는 반드시 확인 작업이 필요하기 때문에 PriorityQueue의 속도가 더 느립니다.
코딩테스트 문제는 Thread-safe를 요구하지 않기 때문에 heapq를 쓰는게 낫습니다.

2번째 코드에서 우선순위 큐를 사용한 부분만 힙으로 바꿔주었습니다.

import sys
import heapq

input = sys.stdin.readline

n = int(input())

cards = []
count = 0

for _ in range(n):
    heapq.heappush(cards, int(input()))

while len(cards) != 1:
    temp = heapq.heappop(cards) + heapq.heappop(cards)
    count += temp
    heapq.heappush(cards, temp)

print(count)

끝 !