[Leetcode] 343. Integer Break

문제 요약

• 알고리즘 분류: dp, 동적 계획법
• 난이도: Medium
• 문제내용:
  • 정수 n이 주어지면 k개의 양의 정수의 합(k > = 2)으로 나누고 그 정수의 곱을 최대화한다.
• 사이트 주소: https://leetcode.com/problems/integer-break/description/ 

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 DP로 풀어야 통과가 되는 문제이다. DP에 대한 자세한 설명은 아래글로 확인해보면 된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

문제 접근방법

  dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다. 일단 각 최대로 나오는것 먼저 확인 해보자.

2 = 1 × 1 = 1
3 = 1 × 2 = 2
4 = 2 × 2 = 4
5 = 2 × 3 = 6
6 = 3 × 3 = 9
7 = 3 × 4 = 12
8 = 2 × 3 × 3 = 18
9 = 3 × 3 × 3 = 27
10 = 3 × 3 × 4 = 36
11 = 2 × 3 × 3 × 3 =54

 1 부터 5나 6까지 했으면  N // 2 × (N // 2 + N % 2)이렇게 되었지만 8부터는 다르다. 그래서 다시 아래를 확인 해보자

1 = 1
2 = 1 × 1 = 1
3 = 1 × 2 = 2
4 = 2 × 2 = 4
5 = 2 × 3 = 6
6 = 3 × 3 = 9
7 = 3 × 4 = 12
8 = 2 × 3 × 3 = 2 × dp[6] = 18
9 = 3 × 3 × 3 = 3 × dp[6] = 27
10 = 3 × 3 × 4 = 3 × dp[7] = 36
11 = 2 × 3 × 3 × 3 = 2 × dp[9] = 54

 7까지는 N // 2 × (N // 2 + N % 2) 통하지만 8부터는 다른 방법으로 접근해야 한다. 그러면 점화식으로 표현 한다면 i, j 반복문으로 1 부터 N까지 돌린다면 아래같은 식이 나온다.

  dp[i]  =  dp[i], j * dp[i - j], j * (i - j) 3개식 중 가장 큰 값으로 저장하면된다. 그러면 시간 복잡도는 O(N ^ 2)이 나온다.

Code

Python

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i // 2 + 1):
                dp[i] = max(dp[i], j * dp[i - j], j * (i - j))

        return dp[n]

Java

import java.util.Arrays;

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

 

 반복문에서 j 부분에서  i / 2 + 1까지 하는 것은 절반 이상일때 탐색 할필요가 없고 dp도 절반 이하에서 값이 더 큰 값이 나오지 않기 때문이다.