343. Integer Break

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Solution が無かったので自分の解法。

まずは10ぐらいまで手作業で実験してみる。

2 : 1x1=1
3 : 1x2=2
4 : 2x2=4
5 : 2x3=6
6 : 3x2x2=9
7 : 3x4=12
8 : 2x3x3=18
9 : 3x3x3=27
10: 3x3x2x2=36

出来るだけ２と３に分割した方が答えに近づきそうな結果が得られたので、貪欲法で解く。

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2

        ans = 1
        while n > 4:
            ans *= 3
            n -= 3

        ans *= n

        return ans