[Leetcode] 343. Integer Break 문제풀이

https://leetcode.com/problems/integer-break/

Integer Break - LeetCode

 

문제 내용

숫자 n이 주어질 때

숫자 n을 쪼개서 더할 수 있는 정수 배열을 만들고, 그 정수 배열의 모든 곱이 가장 큰 값 구하기

 

Example 1:

Input: n = 2

Output: 1

Explanation: 2 = 1 + 1 (정수 배열을 1,1로 쪼갠뒤) , 1 × 1 = 1. (해당 배열을 곱함)

 

문제 풀이

분할정복 개념을 적용할 수 있다.

n을 쪼갰을때 n 이랑 n-i 로 분할되는데 해당 최대값을 서로 곱하거나

n이랑 n-i이랑도 곱하는 경우의 수를 4개로 나눌수 있다.

 

분할 정복에서 발생한 중복되는 부분을 DP로 적용하면 된다.

 

class Solution {
public:
    int dp[59] = {0,};
    
    int integerBreak(int n) {
        if (n <= 2)
            return 1;
        
        if (dp[n])
            return dp[n];

        for (int i = 1; i <= n/2; ++i) {
            dp[n] = max(dp[n], i * (n-i));
            dp[n] = max(dp[n], i * integerBreak(n-i));
            dp[n] = max(dp[n], integerBreak(i) * (n-i));
            dp[n] = max(dp[n], integerBreak(i) * integerBreak(n-i));
        }
        
        return dp[n];
    }
};