C++ 동적 계획법으로 푸는 최대 곱 로프 자르기 문제(DP-36)

이 튜토리얼에서는 최대 곱 로프 자르기(Maximum Product Cutting, DP-36) 문제를 해결하는 방법을 다룹니다.

N미터 길이의 로프가 주어졌을 때, 로프를 여러 개의 정수 길이 조각으로 잘라 각 조각 길이의 곱이 최대가 되도록 만드는 것이 목표입니다. 예를 들어 길이가 10인 로프는 3, 3, 4로 자를 경우 곱이 36으로 가장 커집니다.

예제 코드

#include <iostream>
using namespace std;
// 두 개, 세 개 정수 중 최댓값 구하기
int max(int a, int b) {
    return (a > b)? a : b;
}
int max(int a, int b, int c) {
    return max(a, max(b, c));
}
// 최대 곱 반환
int maxProd(int n) {
    if (n == 0 || n == 1) return 0;
    int max_val = 0;
    for (int i = 1; i < n; i++)
        max_val = max(max_val, i*(n-i), maxProd(n-i)*i);
    return max_val;
}
int main() {
    cout << "Maximum Product is " << maxProd(10);
    return 0;
}

출력 결과

Maximum Product is 36

동작 원리

위 코드는 재귀 호출을 활용한 동적 계획법 접근 방식을 사용합니다. 길이가 n인 로프에서 첫 번째 조각의 길이를 i(1 ≤ i < n)로 정하면, 나머지 (n - i) 미터 역시 같은 방식으로 최적으로 잘라야 합니다. 따라서 모든 가능한 i에 대해 'i × (n - i)'와 'i × maxProd(n - i)' 중 더 큰 값을 비교하여 전체 최댓값을 구합니다.

다만 이 순수 재귀 방식은 동일한 하위 문제를 반복해서 계산하기 때문에 시간 복잡도가 지수적으로 증가합니다. 메모이제이션(memoization)을 적용하거나 반복문 기반의 DP 테이블을 사용하면 시간 복잡도를 O(n²)까지 줄일 수 있습니다.

추가 팁: 수학적 최적해

흥미로운 사실은, 길이가 5 이상인 로프의 경우 최적의 전략은 항상 길이 3의 조각을 최대한 많이 만드는 것이라는 점입니다. 단, 마지막에 1이 남는 경우에는 3 + 1 대신 2 + 2로 자르는 것이 곱이 더 큽니다. 예를 들어 길이 10은 3 + 3 + 4(= 36) 또는 3 + 3 + 2 + 2(= 36)로 자르면 됩니다. 이 성질을 활용하면 O(1) 수준의 수학 공식으로도 답을 구할 수 있습니다.