[Leetcode/JAVA] Integer Break

Problem

https://leetcode.com/problems/integer-break/
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.

Solution

Dynamic Programming을 통해 풀이할 수 있다. bottom-top 방식으로 2부터 시작해서 숫자 i를 구성할 수 있는 정수들을 곱한 값 중 제일 큰 값을 dp[i]에 저장한다.
이를 코드로 표현하면 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]))이다.
가장 큰 값을 저장해야 하므로 Math.max로 dp[i]의 값과 새로 구한 값을 비교해 저장한다. 새로 구하는 값은 n이 4이고 (1, 3) 쌍이 있다면 3은 3을 그대로 곱하는 방법과 3을 쪼개서 곱하는 방법 두 가지가 존재한다. 둘 다 비교하기 위해 Math.max를 한 번 더 사용한다.

Code

class Solution {
    public int integerBreak(int n) {
        if (n <= 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}