막대 자르기(Rod Cutting) 문제란?
길이가 n인 하나의 막대가 주어져 있다고 가정해 보겠습니다. 그리고 막대의 각 길이별 가격이 담긴 목록도 함께 주어집니다. 우리가 해야 할 일은 이 막대를 여러 조각으로 잘라 시장에 팔았을 때 얻을 수 있는 최대 이익을 구하는 것입니다.
최적의 결과를 얻으려면 막대를 여러 위치에서 잘라보면서, 잘라낸 조각들의 가격 합을 서로 비교해야 합니다.
예를 들어, 가격 목록이 prices = [1, 5, 8, 9, 10, 17, 17, 20]이고 막대 길이 n = 8이라고 합시다. 이때 막대를 길이 2와 길이 6으로 잘라 팔면 이익은 5 + 17 = 22가 되며, 이것이 가능한 최대 이익입니다.
해결 접근 방식: 동적 계획법
이 문제는 동적 계획법(Dynamic Programming)을 이용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 크기가 n+1인 배열 profit을 정의합니다. profit[i]는 길이 i인 막대를 잘라 팔 때 얻을 수 있는 최대 이익을 저장합니다.
- profit[0] := 0 으로 초기화합니다. 길이가 0인 막대의 이익은 0입니다.
- i를 1부터 n까지 증가시키며 다음을 반복합니다.
- maxProfit := 음의 무한대로 초기화합니다.
- j를 0부터 i-1까지 증가시키며 다음을 반복합니다.
- maxProfit := max(maxProfit, price[j] + profit[i - j - 1])
- profit[i] := maxProfit
- 최종적으로 profit[n]을 반환합니다.
여기서 price[j]는 첫 번째 조각으로 길이 j+1을 잘라 팔 때의 가격이고, profit[i - j - 1]은 남은 부분에서 얻을 수 있는 최대 이익입니다. 이렇게 작은 부분 문제의 해를 이용해 전체 문제를 해결합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int rodCutting(int price[], int n) {
int profit[n+1];
profit[0] = 0;
int maxProfit;
for (int i = 1; i<=n; i++) {
maxProfit = INT_MIN;
for (int j = 0; j < i; j++)
maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
profit[i] = maxProfit;
}
return maxProfit;
}
int main() {
int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
int rodLength = 8;
cout << rodCutting(priceList, rodLength);
}입력
{1, 5, 8, 9, 10, 17, 17, 20}, 8출력
22
시간 복잡도 분석
이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 최대 이익을 저장하는 배열 때문에 O(n)입니다. 단순한 재귀적 완전 탐색이 지수 시간이 걸리는 것에 비해 훨씬 효율적이며, 이것이 동적 계획법의 강점입니다.