C++ 재귀적 분할 또는 그대로 선택으로 최대값 구하기

개요

이 튜토리얼에서는 숫자를 나누어 계산하거나 그대로 두는 두 가지 방법 중 더 큰 값을 선택하여 최대값을 구하는 프로그램을 다룹니다.

문제의 정의는 다음과 같습니다. 하나의 정수 값이 주어지면, 해당 수를 네 부분으로 재귀적으로 나누거나 그대로 사용하는 방식 중 최대값을 찾아야 합니다. 이를 수식으로 표현하면 다음과 같습니다.

F(n) = max( F(n/2) + F(n/3) + F(n/4) + F(n/5), n )

즉, 각 단계에서 원래 값 n을 그대로 취할지, 아니면 2, 3, 4, 5로 나눈 결과들의 합이 더 큰지를 비교하여 더 큰 쪽을 선택하는 것입니다. 이러한 문제는 동적 계획법(Dynamic Programming)을 활용하면 중복 계산 없이 효율적으로 해결할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 최대 결과값 계산
int findMaximum(int size) {
    int term[size + 1];
    term[0] = 0;
    term[1] = 1;
    int i = 2;
    while(i <= size) {
        term[i] = max(i, (term[i / 2] + term[i / 3] + term[i / 4] + term[i / 5]));
        i = i + 1;
    }
    return term[size];
}

int main() {
    int number = 37;
    cout << "Maximum possible sum: " << findMaximum(number) << endl;
    return 0;
}

실행 결과

Maximum possible sum: 57

코드 설명

위 코드는 동적 계획법을 이용해 작은 값부터 차례대로 계산합니다.

term 배열은 0부터 입력값까지 각 숫자에 대한 최대값을 저장합니다. 초기 조건으로 term[0]은 0, term[1]은 1로 설정합니다.

2부터 입력값까지 반복하면서, 현재 숫자 i를 그대로 사용하는 경우와 term[i/2] + term[i/3] + term[i/4] + term[i/5]를 통해 분할한 경우의 합을 비교합니다. 이때 정수 나눗셈 특성상 나누어떨어지지 않는 값은 자동으로 내림 처리됩니다.

예를 들어 입력값이 37일 때, 37을 여러 단계로 분할하고 각 단계마다 더 유리한 선택을 반복하면 최종적으로 57이라는 최대 합을 얻을 수 있습니다.

마무리

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 재귀 호출 대신 반복문과 배열을 사용함으로써 같은 하위 문제를 반복해서 계산하는 낭비를 제거했으며, 이것이 동적 계획법의 핵심 장점입니다.