PythonでN個のオレンジを食べ切る最短日数を求めるプログラム

台所に n 個のオレンジがあるとしましょう。私たちは毎日、次の3つのルールの中から必ず1つだけを選んでオレンジを食べます。

• ルール1：オレンジを1個食べる
• ルール2：n が偶数なら、n / 2 個食べる
• ルール3：n が3で割り切れるなら、2 × (n / 3) 個食べる

このとき、n 個すべてのオレンジを食べ切るまでに必要な最小の日数を求めるのがこの問題です。

具体例：n = 10 の場合

入力が n = 10 のとき、答えは 4 になります。実際の進め方は以下の通りです。

• 1日目：1個食べる → 残り 10 − 1 = 9 個
• 2日目：6個食べる（2 × (9 / 3)）→ 残り 9 − 6 = 3 個
• 3日目：2個食べる（2 × (3 / 3)）→ 残り 3 − 2 = 1 個
• 4日目：最後の1個を食べる → 残り 0 個

解き方のアプローチ

この問題はメモ化再帰を使うことで効率よく解けます。毎日の選択肢をすべて試す単純な全探索では組み合わせが爆発的に増えてしまいますが、同じ n に対する最小日数は常に一定なので、一度計算した結果をキャッシュしておくのがポイントです。

考え方のポイント

「1個ずつ食べる」という選択肢を毎回直接考慮すると非効率です。そこで、次のように発想を転換します。

• 半分にするには n が偶数である必要があるため、奇数なら n % 2 回「1個食べる」を繰り返して偶数に揃えます。
• 同様に、3で割り切れる状態にするには n % 3 回「1個食べる」が必要です。
• 割り切れたら、それぞれ1日で n / 2 個、または 2 × (n / 3) 個をまとめて食べられます。

これにより、漸化式は次のように表せます。

f(n) = 1 + min( n % 2 + f(n // 2),  n % 3 + f(n // 3) )

また、残りが2個以下であれば1日1個ずつ食べるのが最適なので、f(n) = n（n ≤ 2）が初期条件となります。

アルゴリズムの手順

1. 関数 fun(n) を定義する
2. n がすでに memo に登録されていれば、memo[n] を返す
3. n ≤ 2 なら n をそのまま返す
4. memo[n] に「1 + min(n % 2 + fun(n // 2), n % 3 + fun(n // 3))」を保存する
5. memo[n] を返す
6. メイン側では空の辞書 memo を用意し、fun(n) の結果を返す

Pythonでの実装例

def solve(n):
    def fun(n):
        if n in memo:
            return memo[n]
        if n <= 2:
            return n
        memo[n] = 1 + min(n % 2 + fun(n // 2), n % 3 + fun(n // 3))
        return memo[n]

    memo = {}
    return fun(n)

n = 10
print(solve(n))

入力

10

出力

4

コードの解説

内側の関数 fun() が再帰処理を担当し、辞書 memo が計算済みの結果を保持します。再帰の各段階では「2で割る経路」と「3で割る経路」の2択だけを比較すればよいため、探索範囲が大幅に絞り込まれます。

計算量についても触れておきましょう。n を2と3で割り続けて到達できる数は高々 O((log n)²) 個程度しかないため、メモ化によって全体の計算量は非常に小さく抑えられ、大きな n に対しても高速に動作します。