로드 커팅(Rod Cutting)은 동적 계획법(Dynamic Programming)의 대표적인 문제 중 하나입니다. 길이가 n인 막대(로드) 하나와, 각 길이별 판매 가격이 정리된 가격표가 주어졌을 때, 막대를 여러 조각으로 잘라 시장에 판매하여 얻을 수 있는 최대 수익을 구하는 것이 목표입니다.
막대를 어느 위치에서 자르느냐에 따라 수익이 달라지므로, 가능한 모든 절단 위치를 고려하고 그 결과를 비교하여 최적의 해를 찾아야 합니다.
점화식 정의
f(n)이 길이가 n인 막대를 잘라서 얻을 수 있는 최대 가격을 반환하는 함수라고 정의해 봅시다. 이 함수는 다음과 같은 점화식으로 표현할 수 있습니다.
f(n) := price[i] + f(n – i – 1) 의 최댓값 (i는 0부터 n–1까지)
즉, 첫 번째 조각의 길이를 i로 정하면 남은 길이 (n – i – 1)에 대한 최적해에 첫 조각의 가격을 더한 값들 중 가장 큰 것을 선택하는 방식입니다.
입력 및 출력
입력: 길이별 가격표와 막대의 전체 길이. 이 예제에서 막대의 길이는 8입니다.
출력: 판매 후 얻을 수 있는 최대 이익은 22입니다.
막대를 길이 2와 6으로 나누어 판매하면 이익은 5 + 17 = 22가 됩니다.
알고리즘
rodCutting(price, n)
입력: 가격 리스트, 리스트에 포함된 가격의 개수
출력: 막대를 잘라 판매하여 얻는 최대 이익
Begin 크기가 n+1인 profit 배열을 정의 profit[0] := 0 for i := 1 to n, do maxProfit := -∞ for j := 0 to i-1, do maxProfit := maxProfit와 (price[j] + profit[i-j-1]) 중 큰 값 done profit[i] := maxProfit done return maxProfit End
이 알고리즘은 작은 길이부터 차례대로 최적해를 계산하여 배열에 저장하고, 이를 활용해 더 긴 막대의 최적해를 구하는 상향식(Bottom-up) 동적 계획법 방식입니다.
C++ 예제 코드
#include <iostream>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int rodCutting(int price[], int n) { // 가격표와 길이 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 << "Maximum Price: "<< rodCutting(priceList, rodLength);
}실행 결과
Maximum Price: 22
시간 복잡도
막대의 각 길이 i에 대해 내부 반복문이 i번 실행되므로, 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 길이별 최대 이익을 저장하는 배열 때문에 O(n)입니다. 단순 재귀로 모든 경우를 탐색하면 지수 시간이 걸리지만, 동적 계획법을 사용하면 중간 결과를 재활용하여 효율적으로 문제를 해결할 수 있습니다.