[JS] Integer Break

🔒 문제 (LeetCode 343)

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Constraints:

• 2 <= n <= 58

 

🌊 입출력

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

 

---

 

🔑 해결

🌌 알고리즘 - DP

더해서 n이 되고 곱해서 최대값이 되는 수들은 짝수일 경우 (n/2)*(n/2)이고 홀수일 경우 (n-1)/2 * (n+1)/2 이다.

여기서 두 수 중 더 나눌 수 있다면 같은 방법을 나누어 최종적으로 쪼갠 숫자들의 곱이 최대값이다. 

이 떄 숫자들은 모두 3이하가 되는데 1은 고려하지 않으므로 2 또는 3으로만 이루어지게 된다.

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    if(n === 2) return 1
    if(n === 3) return 2
 
    let total = 1
    
    while(n > 4) {
        total *= 3
        n -= 3
    }
    total *= n
    
    return total
};