문제 소개
하나의 자연수 n이 주어졌을 때, 합이 정확히 n이 되도록 두 개 이상의 수로 나누고, 그 수들의 곱이 최대가 되도록 만들어야 하는 문제입니다. 우리가 최종적으로 구해야 할 값은 바로 이 곱의 최댓값입니다.
예를 들어 입력이 n = 12라고 가정해 봅시다. 3 + 3 + 3 + 3 = 12를 만족하며, 곱은 3 × 3 × 3 × 3 = 81이 됩니다. 다른 방식으로 나누는 것보다 이 조합이 가장 큰 곱을 만들어 내므로 출력은 81입니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)과 재귀 호출을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 단계에서 숫자 i 하나를 선택하고, 남은 값(n − i)에 대해 같은 과정을 반복하면서 얻을 수 있는 최대 곱을 비교하는 것입니다.
알고리즘은 다음과 같이 진행됩니다.
- dp() 함수를 정의합니다. 이 함수는 n을 인자로 받습니다.
- 기저 사례: n이 0이면 1을 반환합니다. 더 이상 나눌 수 없음을 의미합니다.
- ans를 0으로 초기화합니다.
- i를 1부터 n까지 반복하면서, ans와 (i × dp(n − i)) 중 더 큰 값을 ans에 저장합니다.
- 반복이 끝나면 ans를 반환합니다.
- 메인 메소드에서는 dp(n)의 결과를 그대로 반환합니다.
파이썬 구현 예제
class Solution:
def solve(self, n):
def dp(n):
if n == 0:
return 1
ans = 0
for i in range(1, n + 1):
ans = max(ans, i * dp(n - i))
return ans
return dp(n)
ob1 = Solution()
print(ob1.solve(12))
입력
12
출력
81
성능 개선 팁
위 구현은 재귀 호출이 중복되어 시간 복잡도가 지수적으로 증가할 수 있습니다. 파이썬의 functools.lru_cache 데코레이터를 사용하면 이미 계산한 값을 캐싱하여 실행 속도를 크게 향상시킬 수 있습니다.
from functools import lru_cache
class Solution:
def solve(self, n):
@lru_cache(maxsize=None)
def dp(n):
if n == 0:
return 1
ans = 0
for i in range(1, n + 1):
ans = max(ans, i * dp(n - i))
return ans
return dp(n)
참고로 수학적으로 흥미로운 사실은, 곱을 최대화하려면 가능한 한 많은 3으로 나누는 것이 유리하다는 점입니다. 3이 곱의 증가율이 가장 높기 때문입니다. 이 성질을 활용하면 O(1) 수준의 수학 공식으로도 문제를 풀 수 있습니다.