[LeetCode] 343. Integer Break

https://leetcode.com/problems/integer-break/

Integer Break - LeetCode

Integer Break - Medium

 

어떤 수를 여러개의 수의 합으로 쪼갰을때, 이 수들의 곱 중 가장 큰 수를 구하는 문제다.

O(n)의 간단한 풀이가 있다고 하는데, O(n)은 아직 찾지 못했다.

그 중엔 3의 개수를 가장 많게 하면 된다는 풀이도 있었는데 나중에 증명해봐야겠다.

나의 풀이는 아래와 같다. (O(n^2))

 

가장 먼저 정답을 저장할 배열 M을 만들어준다.

n이 2이상이므로,

2일 경우에는 1+1 뿐이므로 1이 된다.

3일 경우엔 1+1+1 이나 1+2가 되는데 이는 1X1X1 과 1X2 중 고르는 문제다.

이를 잘 보면 1X(2를 만드는 경우) 가 된다.

4의 경우엔 1+1+1+1, 1+1+2, 2+2, 3+1 이 되는데 이것은 1X1X1X1, 1X3, 1X1X2, 2X2 중 고르는 문제로,

역시나 잘 보면 1X(3을 만드는 경우) 또는 (2를 만드는 경우)X(2를 만드는 경우) 로 볼 수가 있다.

즉 M[4] = M[1] * M[3] 과 M[2] * M[2] 중 최대값이 된다.

다만 문제는, 2를 보면 우리가 바로 위에서 원하는 M[2] 값은 2인데, 저장한 값은 1이 된다.

그러므로 구하고자 하는 n을 제외한 값은 자기자신도 포함하여 고려해주자.

 

즉, 식을 세우면, n보다 작을때만 M[i]를 먼저 i로 놔주고, 0<j<=i/2 인 j에 대해

M[i] = max(M[i], M[j] * M[i-j] 를 해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int integerBreak(int n) {
        int M[60] = {};
        M[1] = 1;
        for (int i=2; i<=n; i++) {
            if (i!=n) M[i] = i;
            for (int j=1; j<=i/2; j++) M[i] = max(M[i], M[j]*M[i-j]);
        }
        return M[n];
    }
};