[LeetCode] 343. Integer Break

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

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 정수론, 수학

문제 난이도 : Medium

 

문제

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.

 

정수 N이 주어진다. 2개 이상의 정수의 합으로 쪼개서 그 수들의 곱이 최대가 되는 값을 구하여라.

 

풀이

쪼개진 수의 곱이 최대가 되게 하려면, 가능한 많이 3으로 쪼개야 한다.

n=9라고 했을 때, 3+3+3일때 최댓값인 27이 나온다.

n=10이라고 했을 때, 3+3+4, 최댓값 36이 나온다.

n=11이라고 했을 때, 3+3+3+2 최댓값 54가 나온다.

 

5의 경우, 2+3 => 2*3=6으로, 2나 3으로 나누는 게 커질 수 있다는 것을 알아 2나 3으로 쪼개는 게 가장 크게 만드는 방법임을 알았고,

6의 경우 2+2+2 => 2*2*2=8, 3+3=> 3*3 = 9라는 것을 보아, 최대한 많은 3을 만드는 것이 최선이라고 생각했다.

그래서, 3^(3의개수)가 3의배수 기준에서의 최대값임을 알았고,

3으로 나눴을 때 나머지가 1인 경우에서는..

4를 예시로 했을 때, 2*2 = 4, 3*1 = 3인것으로 보아, 나머지가 1인 경우에는 3을 하나 덜 만들고, 2*2형태로 쪼개는 게 가장 큼을 알았다.

그리고, 나머지가 2인 경우, 최대한 많이 3을 만들고 나서 그냥 2를 곱해주면 된다.

 

 

결론은

n % 3 == 0일때, 3^(n/3)이 최대이고,

n % 3 == 1일때, 3^(n/3-1) * 4가 최대,

n % 3 == 2일때, 3^(n/3) * 2가 최대임을 발견할 수 있었다.

 

코드

C++

class Solution {
public:
    int integerBreak(int n) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        
        if(n <= 3) return n-1;

        if(n%3 == 0) {
            return (int)pow(3, n/3);
        } else if(n%3 == 1) {
            return (int)pow(3, (n/3)-1) * 4;
        } else {
            return (int)pow(3, n/3)*2;
        }
    }
};