JAVA 코드 - 알고리즘 기초: 정수 분할 최대 곱셈 문제

정수 분할 최대 곱셈 문제

문제 설명: 정수 n을 지정하여 최소 두 정수의 총합으로 분해하고 이 정수의 곱셈을 최대화합니다.당신이 얻을 수 있는 가장 큰 결과를 되돌려줍니다.예를 들어 n=2를 주고 1(2=1+1)을 되돌려준다.n = 10을 주고 36(10 = 3 + 3 + 4)을 반환합니다.주: n이 2보다 작지 않고 58보다 작지 않다고 생각할 수 있습니다.
알고리즘 분석
제목에 설정된 조건에 따라 정수 n의 수치 범위는 2<=n<=58로 분석한다. n=2시: n=1+1;result=1*1=1 n=3시: 1+2 또는 1+1+1으로 나눌 수 있지만 분명히 1+2로 나눌 수 있다. 획득한 곱셈 최대 n=4시: 1+3 또는 2+2로 나눌 수 있지만 분명히 2+2로 나눌 수 있다. 획득한 곱셈 최대 n=5시: 2+3, 획득한 곱셈 최대 n=6시: 3+3, 획득한 곱셈 최대 n=7시: 3+4로 나눌 수 있다.획득한 곱셈 최대 n=8 시: 3+3+2, 획득한 곱셈 최대 n=9 시: 3+3+3, 획득한 곱셈 최대 n=10 시: 3+3+4로 나눌 수 있다. 획득한 곱셈 최대는 상기 내용을 관찰한 결과 n=5에서 시작하여 나누는 결과에 모두 숫자 3이 있음을 알 수 있다.다음 숫자, 예를 들어 11은 먼저 3개를 뜯은 다음에 나머지 8이 어떻게 나누는지 볼 수 있다.
알고리즘 설계

public static int interBreakProblem(int n) {

        if(n==2 || n==3)
            return n-1;
        if(n==4) return n;
        int result=1;
        while(n>4) {
            result*=3;
            n-=3;
        }

        return result*n;

    }

알고리즘 설계2: DP
DP를 사용할 때 가장 중요한 것은 상태 방정식을 밀어내는 것입니다.

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

다음과 같은 방법으로 테스트를 수행할 수 있습니다.

public static void main(String[] args) {
        // TODO Auto-generated method stub

        int n=11;
        int result=integerBreak(n);
        System.out.println("RESULT IS: "+result);

        int res=interBreakProblem(n);
        System.out.println("RESULT IS: "+res);

    }

실행 결과:
RESULT IS: 54 RESULT IS: 54
상기 두 방법의 집행 결과는 같다.상호 검증.
(끝)