2024.03.07 - Integer break

[wlsgh7608]

문제 - 링크

문제 풀이

• 2개 이상의 자연수의 합으로 만드는 N에 대하여 각각의 자연수의 곱의 최댓값 구하기

i을 만드는 데 가장 큰 최댓값 구하기

• i보다 작은 자연수 j에 대하여 d[i]의 값은 d[j] * d[i-j]로 만들어 짐
• 각각에 대하여 최댓값 구하기
• 여러 자연수의 곱보다 단일 숫자의 값이 더 클 수도 있음

            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
            if (i < n) {
                dp[i] = Math.max(dp[i], i);
            }

코드

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];

        dp[1] = 1;
        for (int i = 1; i <= n; i++) {
            // dp[1]*dp[1]
            for (int j =1;j<i;j++){
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
            if(i<n){
                dp[i] = Math.max(dp[i], i);
            }
        }

        return dp[n];
    }
}

시간, 공간 복잡도

• 시간 복잡도 : O(N*2)
• 공간 복잡도 : O(N)

실행 시간