
Loading...
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
出来るだけ2と3に分割した方が答えに近づきそうな結果が得られたので、貪欲法で解く。
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
コメント