문제 소개
양의 정수 n이 주어졌을 때, 이를 최소 두 개 이상의 양의 정수의 합으로 분할하고, 그 수들의 곱이 최대가 되도록 만드는 문제입니다.
예를 들어 n = 10이라면, 10 = 3 + 3 + 4로 나눌 때 곱이 3 × 3 × 4 = 36으로 가장 크므로 정답은 36이 됩니다.
접근 방법 (동적 계획법)
이 문제는 메모이제이션(memoization)을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.
- solve(n, dp, flag) 메서드를 정의합니다.
- n이 0이면 1을 반환합니다. (분할이 완료된 기저 조건)
- dp[n]이 -1이 아니라면 이미 계산된 값이므로 그대로 반환합니다.
- flag가 설정되어 있으면(첫 호출) end = n - 1, 그렇지 않으면 end = n으로 지정합니다. 첫 번째 분할에서는 적어도 두 개의 수로 나눠야 하기 때문입니다.
- ret = 0으로 초기화한 뒤, i를 1부터 end까지 순회하며 ret = max(ret, i × solve(n - i, dp, false))를 계산합니다.
- dp[n]에 ret을 저장하고 반환합니다.
- 메인 함수에서는 크기가 n + 1인 dp 배열을 만들고 모든 값을 -1로 초기화한 후, solve(n, dp)를 호출하여 결과를 반환합니다.
여기서 flag의 역할이 중요합니다. 처음에는 n 자체를 하나의 "분할"로 사용하는 것을 막기 위해 n - 1까지만 시도하지만, 이후 재귀 호출에서는 n 전체 범위를 허용하여 최적의 곱을 찾습니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int n, vector <int>& dp, bool flag = true){
if(n == 0) return 1;
if(dp[n] != -1) return dp[n];
int end = flag? n - 1: n;
int ret = 0;
for(int i = 1; i <= end; i++){
ret = max(ret, i * solve(n - i, dp, false));
}
return dp[n] = ret;
}
int integerBreak(int n) {
vector <int>dp(n + 1, -1);
return solve(n, dp);
}
};
main(){
Solution ob;
cout << (ob.integerBreak(10));
}입력
10
출력
36
마무리
이 알고리즘은 각 부분 문제를 한 번씩만 계산하므로 시간 복잡도는 O(n²), 공간 복잡도는 O(n)입니다. 메모이제이션 덕분에 중복 계산 없이 빠르게 최대 곱을 구할 수 있습니다. 추가로 참고하자면, 수학적으로는 3을 최대한 많이 사용하는 것이 유리하며(3×3 > 2×2×2가 아니라 오히려 3+3일 때 곱이 더 큼), 남은 값이 1이면 2와 결합하는 전략이 최적임이 알려져 있습니다.