숫자를 세 부분으로 나누어 얻을 수 있는 최대 합 구하기

하나의 숫자가 주어졌을 때, 그 숫자를 n/2, n/3, n/4로 나누는 작업을 반복하여 세 부분씩 쪼개고, 이렇게 나누어 얻을 수 있는 최대 합을 구하는 것이 이번 문제의 목표입니다.

예를 들어 50은 {25, 16, 12}로 나눌 수 있습니다. 이후 집합 {25, 16, 12}에 속한 각 숫자를 다시 세 부분으로 나누는 과정을 반복합니다. 모든 나누기가 끝나면 각 경우의 합을 계산하여 그중 최댓값을 찾습니다.

이 문제는 재귀 호출로도 해결할 수 있지만, 재귀 방식에서는 동일한 값을 여러 번 중복 계산하게 됩니다. 따라서 동적 계획법(Dynamic Programming)을 활용해 한 번 계산한 결과를 테이블에 저장해 두면 불필요한 연산을 줄여 실행 시간을 크게 단축할 수 있습니다.

핵심 아이디어는 단순합니다. 어떤 수 i에 대해 i를 2, 3, 4로 나눈 몫들의 최대 합이 원래 값 i보다 작다면, 굳이 나누지 않고 i 그대로를 선택하는 것이 더 유리하다는 점입니다. 즉, 매 단계마다 i 자신과 sums[i/2] + sums[i/3] + sums[i/4] 중 더 큰 값을 택하면 됩니다.

입력과 출력

입력:
주어진 숫자가 12라고 가정합니다.
출력:
답은 13입니다.
먼저 12를 (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13으로 나눕니다.
다음으로 6을 세 부분으로 나누면 (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6입니다.
4와 3을 나누면 각각 최대 4와 3을 얻을 수 있습니다.
모든 값 중 최댓값은 13입니다.

알고리즘

maxBreakSum(n)

입력: 주어진 숫자 n

출력: 나누기를 마친 후의 최대 합

Begin
    크기가 n+1인 배열 sums를 선언한다
    sums[0] := 0, sums[1] := 1

    for i in range 2 to n, do
        sum[i] := i와 (sums[i/2] + sums[i/3] + sums[i/4]) 중 최댓값
    done
    return sums[n]
End

C++ 예제 코드

#include<iostream>
#define MAX 1000000
using namespace std;

int max(int a, int b) {
   return (a>b)?a:b;
}

int maxBreakSum(int n) {
   int sumArr[n+1];
   sumArr[0] = 0, sumArr[1] = 1;    // 0과 1의 최대 합은 각각 0과 1

   for (int i=2; i<=n; i++)    // 2부터 n까지 차례로 최대 합 계산
      sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i);    // 숫자를 2, 3, 4로 나눈 결과와 자기 자신 비교
   return sumArr[n];
}

int main() {
   int n;
   cout << "Enter a number: "; cin >> n;
   cout << "Maximum sum after breaking: " << maxBreakSum(n);
}

실행 결과

Enter a number: 12
Maximum sum after breaking: 13

위 코드는 2부터 n까지 작은 문제부터 순서대로 해결하는 상향식(bottom-up) 동적 계획법으로 동작합니다. 각 숫자의 최대 합을 배열에 미리 저장해 두기 때문에, 재귀 방식에서 발생하는 중복 계산 없이 O(n) 시간 복잡도로 답을 구할 수 있습니다.