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

1. 문제를 처음 봤을 때

처음에는 단순히
“카드를 합치면 비용이 든다 → 그냥 순서대로 더하면 되지 않나?”
라고 생각했다.

하지만 예시를 보면

• (10 + 20) + (30 + 40) = 100
• (10 + 40) + (50 + 20) = 120

합치는 순서에 따라 비용이 달라진다

여기서 핵심은

“어떤 순서로 합쳐야 최소가 되는가?”

---

2. 처음 접근 (잘못된 방식)

처음에는 이런 식으로 구현했다.

answer += answer + heapq.heappop(heap)

즉,

• 이전 결과(answer)를 계속 재활용하면서 더하는 방식

하지만 이건 문제의 구조를 잘못 이해한 것이다.

 왜 틀렸는가?

• answer는 “총 비용”이지
• “카드 묶음”이 아니다

나는 answer를 카드 묶음처럼 사용해버림

---

3. 핵심 깨달음

이 문제에서 중요한 건 딱 하나였다.

“합친 카드 묶음도 다시 하나의 묶음으로 취급해야 한다”

즉,

1. 두 묶음을 합친다
2. 그 결과를 다시 후보에 넣는다
3. 다시 가장 작은 두 개를 선택한다

이 흐름이 반복되어야 한다.

---

4. 올바른 접근: 최소 힙 (Priority Queue)

그래서 필요한 게 바로 최소 힙이다.

이유는 간단하다.

매번 “가장 작은 두 묶음”을 빠르게 꺼내야 하기 때문

---

5. 최종 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
heap = []
answer = 0

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

while len(heap) > 1:
    card_sum = heapq.heappop(heap) + heapq.heappop(heap)
    answer += card_sum
    heapq.heappush(heap, card_sum)

print(answer)

 

---

6. 왜 최적인가?

이 문제는 사실 구조적으로

“항상 작은 것부터 합치는 것이 전체 비용을 최소화한다”

는 성질을 가진다.

직관적으로 보면

• 큰 값끼리 먼저 합치면 → 이후 계속 큰 비용이 누적됨
• 작은 값끼리 먼저 합치면 → 비용 증가를 최소화 가능

이게 바로 그리디 전략이 성립하는 이유다.

---

7. 시간복잡도

• 힙 연산: O(log N)
• 총 반복: N번

→ 전체: O(N log N)

N = 100,000까지 충분히 통과 가능