🔪 막대 자르기 최소 비용 - 접근법 비교 분석
📌 문제 소개
[귀찮음](https://www.acmicpc.net/problem/16208) 문제소개합니다.
🔍 문제 분석
처음 문제를 봤을 때 몇 가지 관점에서 접근해봤다:
- 총 길이가 정해져 있고 잘라야 하는 길이도 정해져 있다.
- n개의 막대를 만들려면 n-1번 자르는 연산이 필요하다.
- 자르는 순서에 따라 비용이 달라질 수 있다고 생각했다.
🧩 처음 시도한 접근법 DP = 행렬 체인 곱셈 스타일 접근
첫 번째로 떠올린 접근법은 동적 계획법(DP)이다. 이 문제가 행렬 체인 곱셈(Matrix Chain Multiplication) 문제처럼 느껴졌기 때문이다. 행렬 체인 곱셈(Matrix Chain Multiplication) 문제는 여러 행렬을 곱할 때 연산 횟수를 최소화하는 괄호 배치를 찾는 문제다. 이 문제와 막대 자르기 문제는 구조적으로 유사하다고 생각했다.
💡 기본 아이디어
이 접근법의 핵심은 분할 정복과 동적 계획법이다. 전체 문제를 작은 부분 문제로 나누고, 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구한다.
- dp[i][j]는 i번째부터 j번째까지의 막대를 자르는 최소 비용을 의미한다.
- 모든 가능한 분할점 k에 대해, dp[i][k] + dp[k+1][j] + 자르는 비용을 계산한다.
- 그중 최소값이 최적해가 된다.
🧠 구현 코드
def min_cutting_cost_mcm(lengths):
n = len(lengths)
# dp[i][j] = i번째부터 j번째까지의 막대를 자르는 최소 비용
dp = [[0] * n for _ in range(n)]
# 누적 합 계산
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + lengths[i]
# 길이가 2부터 n까지의 부분 문제 해결
for length in range(2, n + 1): # 부분 문제의 크기
for i in range(n - length + 1): # 시작 인덱스
j = i + length - 1 # 끝 인덱스
# 현재 구간의 총 길이
current_sum = prefix_sum[j + 1] - prefix_sum[i]
# dp[i][j]를 무한대로 초기화
dp[i][j] = float('inf')
# 모든 가능한 분할점 k에 대해 최소 비용 계산
for k in range(i, j):
# 비용 = 왼쪽 부분 비용 + 오른쪽 부분 비용 + 전체 구간 길이
cost = dp[i][k] + dp[k+1][j] + current_sum
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
📊 성능 분석
- 시간 복잡도: O(n³) - 세 개의 중첩된 루프가 있다.
- 공간 복잡도: O(n²) - dp 테이블과 prefix_sum 배열이 필요하다.
📝 예시 실행 과정
입력: [3, 5, 4, 2]
- 초기화:
- dp 배열을 0으로 초기화
- prefix_sum = [0, 3, 8, 12, 14]
- 길이 2인 부분 문제:
- dp[0][1] = min_k{ dp[0][0] + dp[1][1] + (3+5) } = 0 + 0 + 8 = 8
- dp[1][2] = min_k{ dp[1][1] + dp[2][2] + (5+4) } = 0 + 0 + 9 = 9
- dp[2][3] = min_k{ dp[2][2] + dp[3][3] + (4+2) } = 0 + 0 + 6 = 6
- 길이 3인 부분 문제:
- dp[0][2] = min{
- dp[0][0] + dp[1][2] + (3+5+4) = 0 + 9 + 12 = 21
- dp[0][1] + dp[2][2] + (3+5+4) = 8 + 0 + 12 = 20 } = 20
- dp[1][3] = min{
- dp[1][1] + dp[2][3] + (5+4+2) = 0 + 6 + 11 = 17
- dp[1][2] + dp[3][3] + (5+4+2) = 9 + 0 + 11 = 20 } = 17
- dp[0][2] = min{
- 길이 4인 부분 문제:
- dp[0][3] = min{
- dp[0][0] + dp[1][3] + (3+5+4+2) = 0 + 17 + 14 = 31
- dp[0][1] + dp[2][3] + (3+5+4+2) = 8 + 6 + 14 = 28
- dp[0][2] + dp[3][3] + (3+5+4+2) = 20 + 0 + 14 = 34 } = 28
- dp[0][3] = min{
따라서 이 접근법에서 계산된 최소 비용은 28이다... 그런데 정답은 71이다! 여기서 문제가 있음을 알 수 있다.
❌ 왜 이 접근법이 틀렸나?
행렬 체인 곱셈 스타일 접근은 자르는 비용을 전체 구간의 길이로 잘못 계산했다. 문제에서는 "자르는 비용 = 두 부분의 길이의 곱"인데, 구현에서는 "자르는 비용 = 전체 구간의 길이"로 계산했다.
이 방식이 틀린 이유는 막대를 자를 때 드는 비용의 계산 방식이 문제 정의와 다르기 때문이다. 자르는 비용은 단순히 구간의 길이가 아니라, 자르는 두 부분의 길이의 곱이어야 한다.
🌲 허프만 코딩 스타일 접근
허프만 코딩(Huffman Coding)은 가변 길이 접두어 코드를 만드는 알고리즘으로, 항상 가장 작은 두 노드를 선택하여 합치는 방식이다. 막대 자르기 문제에서도 비슷한 접근이 가능하지 않을까 생각했다.
💡 기본 아이디어
이 접근법의 핵심은 **탐욕적 알고리즘(Greedy Algorithm)**이다. 항상 가장 작은 두 막대를 선택하여 자르는 것이 최적이라고 가정한다.
- 모든 막대 길이를 최소 힙(Min Heap)에 넣는다.
- 가장 작은 두 막대를 꺼내서 합친다.
- 합친 비용을 더하고, 합쳐진 막대를 다시 힙에 넣는다.
- 힙에 하나의 막대만 남을 때까지 반복한다.
🧠 구현 코드
import heapq
def min_cutting_cost_huffman(lengths):
n = len(lengths)
# n=1인 경우 자를 필요 없음
if n == 1:
return 0
# 최소 힙(우선순위 큐)을 사용하여 항상 가장 작은 두 막대를 선택
heap = lengths.copy()
heapq.heapify(heap)
total_cost = 0
# n-1번 자르기 수행
while len(heap) > 1:
# 가장 작은 두 막대를 선택
first = heapq.heappop(heap)
second = heapq.heappop(heap)
# 두 막대를 합치는 비용 계산
current_cost = first + second
total_cost += current_cost
# 합쳐진 막대를 다시 힙에 넣기
heapq.heappush(heap, current_cost)
return total_cost
📊 성능 분석
- 시간 복잡도: O(n log n) - 힙 연산이 log n 시간이 걸리고, 최대 n-1번 수행된다.
- 공간 복잡도: O(n) - 힙에 최대 n개의 요소가 저장된다.
📝 예시 실행 과정
입력: [3, 5, 4, 2]
- 초기화:
- heap = [2, 3, 4, 5]
- 첫 번째 반복:
- 가장 작은 두 막대: 2, 3
- 비용: 2 + 3 = 5
- total_cost = 5
- heap = [4, 5, 5]
- 두 번째 반복:
- 가장 작은 두 막대: 4, 5
- 비용: 4 + 5 = 9
- total_cost = 5 + 9 = 14
- heap = [5, 9]
- 세 번째 반복:
- 가장 작은 두 막대: 5, 9
- 비용: 5 + 9 = 14
- total_cost = 14 + 14 = 28
- heap = [14]
따라서 이 접근법에서 계산된 최소 비용은 28이다... 그런데 정답은 71이다! 역시 문제가 있다.
❌ 왜 이 접근법이 틀렸나?
허프만 코딩 스타일 접근은 막대를 합치는 방식으로 문제를 해석했다. 하지만 이 문제는 합치는 게 아니라 자르는 문제다. 또한, 허프만 코딩에서는 빈도수가 낮은 문자부터 합치는 것이 최적이지만, 막대 자르기에서는 그런 보장이 없다.
이 방식이 틀린 이유는 문제의 본질을 잘못 해석했기 때문이다. 문제는 하나의 큰 막대를 여러 개의 작은 막대로 자르는 것이고, 비용은 자르는 지점에서의 두 부분의 길이의 곱이다.
🌟 최종 접근법: 모든 쌍의 곱의 합
문제를 깊이 분석한 결과, 자르는 순서에 관계없이 최종 결과는 모든 막대 쌍의 길이 곱의 합과 같다는 사실을 발견했다.
💡 기본 아이디어
이 접근법의 핵심은 수학적 직관이다. 어떤 순서로 자르든, 결국은 모든 가능한 막대 쌍의 길이 곱이 한 번씩 더해진다.
- 각 막대 길이 aᵢ에 대해, aᵢ × (총 길이 - aᵢ)를 계산한다.
- 이 값들의 합을 구한다.
- 각 쌍이 두 번 계산되므로, 결과를 2로 나눈다.
🧠 구현 코드
def min_cutting_cost_optimal(lengths):
n = len(lengths)
if n == 1:
return 0
# 모든 막대의 길이 합 계산
total_length = sum(lengths)
# 각 막대에 대해 비용 계산
total_cost = 0
for length in lengths:
# 비용 = (전체 길이 - 현재 막대 길이) * 현재 막대 길이
total_cost += (total_length - length) * length
# 중복 계산된 부분 제거 (각 쌍이 두 번 계산됨)
return total_cost // 2
📊 성능 분석
- 시간 복잡도: O(n) - 모든 막대를 한 번씩만 순회한다.
- 공간 복잡도: O(1) - 추가 공간이 거의 필요 없다.
📝 예시 실행 과정
입력: [3, 5, 4, 2]
- 총 길이 계산:
- total_length = 3 + 5 + 4 + 2 = 14
- 각 막대에 대한 비용 계산:
- 3 × (14 - 3) = 3 × 11 = 33
- 5 × (14 - 5) = 5 × 9 = 45
- 4 × (14 - 4) = 4 × 10 = 40
- 2 × (14 - 2) = 2 × 12 = 24
- 합계: 33 + 45 + 40 + 24 = 142
- 중복 제거:
- 142 ÷ 2 = 71
따라서 최종 비용은 71이다. 이것이 정답이다!
✅ 왜 이 접근법이 맞나?
이 문제의 핵심 통찰은 다음과 같다:
- 막대를 자르는 순서에 관계없이, 최종적으로는 a₁, a₂, ..., aₙ의 n개의 막대가 만들어진다.
- 어떤 순서로 자르든, 각 막대 쌍 (aᵢ, aⱼ)는 정확히 한 번씩 자르는 비용에 기여한다.
- 총 비용은 a₁×a₂ + a₁×a₃ + ... + aₙ₋₁×aₙ과 같다.
- 이는 수학적으로 ∑ aᵢ × (∑ aⱼ - aᵢ) ÷ 2와 같다.
🧮 수학적 증명
n=4인 경우, 자르는 비용은 다음과 같이 계산할 수 있다:
- 3 × 5 + 3 × 4 + 3 × 2 + 5 × 4 + 5 × 2 + 4 × 2 = 15 + 12 + 6 + 20 + 10 + 8 = 71
이는 우리가 계산한 값과 정확히 일치한다!
아니 왜 자꾸 이런거 내요?
⚡ 왜 이 접근법이 맞는가?
- 자르는 순서는 중요하지 않다: 결국 같은 길이의 막대들을 만들어야 하기 때문에, 어떤 순서로 자르든 총 비용은 동일하다.
- 모든 가능한 쌍의 곱의 합: 총 비용은 결국 a₁×a₂ + a₁×a₃ + ... + aₙ₋₁×aₙ 로 표현된다.
- 수학적 표현: 각 막대 길이 aᵢ에 대해 aᵢ × (total_length - aᵢ)의 합을 계산하면 모든 쌍의 곱을 두 번씩 더하게 된다. 따라서 결과를 2로 나눠야 한다.
🚀 트러블슈팅 정리
- DP 접근법
행렬 체인 곱셈처럼 생각했지만, 이 문제에서는 자르는 순서가 결과에 영향을 미치지 않기 때문에 적절하지 않았다. - 허프만 코딩 스타일
가장 작은 두 막대를 먼저 합치는 방식도 이 문제의 특성과 맞지 않았다. - 수학적 접근
결국 총 비용은 모든 쌍의 곱의 합이라는 통찰이 가장 중요했다. 이는 시간 복잡도 O(n)의 효율적인 해결책을 제공한다.
🎯 결론
이 문제는 알고리즘적 접근보다 수학적 통찰이 더 중요한 문제였다. 처음에는 복잡한 DP나 그리디 알고리즘을 생각했지만, 결국 문제의 본질을 이해하고 수학적으로 접근하니 간단하고 효율적인 O(n) 시간 복잡도의 해결책을 찾을 수 있었다.
복잡한 문제일수록 기본으로 돌아가서 문제의 본질을 이해하는 것이 중요하다는 교훈을 얻을 수 있었다.🚀