【Python】合計がnに等しくなる数の組み合わせで積を最大化するプログラム

ある整数 n が与えられたとき、「合計が n に等しくなる2つ以上の正の整数」を見つけ、それらの積を最大化する問題を考えます。最終的な答えとして、その最大の積を求める必要があります。

例えば、入力が n = 12 の場合、出力は 81 になります。これは、3 + 3 + 3 + 3 = 12 となり、その積は 3 × 3 × 3 × 3 = 81 となるためです。

解法のアプローチ

この問題は、動的計画法(DP)の考え方を使った再帰関数で効率よく解くことができます。手順は以下の通りです。

• 関数 dp() を定義します。引数として n を受け取ります。
• n が 0 の場合は 1 を返します(これが再帰の終了条件となります)。
• 変数 ans を 0 で初期化します。
• i を 1 から n までループさせ、以下を繰り返します。
  • ans と「i × dp(n − i)」のうち大きい方を ans に代入します。
• ループ終了後、ans を返します。
• メイン処理からは dp(n) を呼び出して結果を返します。

ここで重要なのは、各分割位置 i について「残りの n − i をさらに分割した場合の最大積」に i を掛けた値を比較している点です。これにより、全体の最適な分割方法が自然に導き出されます。

実装例

以下のコードで実際の動作を確認してみましょう。

class Solution:
    def solve(self, n):
        def dp(n):
            if n == 0:
                return 1
            ans = 0
            for i in range(1, n + 1):
                ans = max(ans, i * dp(n - i))
            return ans
        return dp(n)
ob1 = Solution()
print(ob1.solve(12))

入力

12

出力

81

補足：数学的な背景

実はこの問題には有名な数学的性質があり、数を 3 にできるだけ多く分割するのが最適であることが知られています。ただし、余りが 1 の場合は 3 + 1 を 2 + 2 に置き換える方が積が大きくなります。上記の DP 実装は、こうしたケース分けを意識せずとも自動的に最適解を導いてくれる汎用的なアプローチです。