「整数を1にする」とは？
整数Xが与えられたとき、次の3つの操作だけでXを1にする最小操作回数を求める問題です。
- •÷3 — Xが3の倍数のときだけ、3で割ります。
- •÷2 — Xが偶数のときだけ、2で割ります。
- •−1 — Xから1を引きます。
AlgoNoteでは、この問題を「おもちゃ屋の魔法カウンターを最小のボタン押下で1にする」という話で可視化します。
なぜグリディは間違うのか？
「できるだけ大きく割れば速い」という直感（グリディ）は、この問題では間違いです。
X = 10を見てみましょう。
- •グリディ（偶数だから÷2優先）: 10 → 5 → 4 → 2 → 1 = 4回
- •正解: 10 → 9(−1) → 3(÷3) → 1(÷3) = 3回
先に−1して9にすると÷3を二回使えます。目の前の大きな割り算が常に最善とは限らない——これがDPが必要な理由です。
DPの漸化式
dp[i]を「iを1にする最小操作回数」と定義します。
- •基底条件:
dp[1] = 0（すでに1なので操作不要） - •漸化式:
dp[i] = 1 + min(
dp[i - 1], // −1 (常に可能)
dp[i / 2] if i % 2 == 0, // ÷2 (偶数のときのみ)
dp[i / 3] if i % 3 == 0 // ÷3 (3の倍数のときのみ)
)iに到達する直前の状態は i-1, i/2, i/3 のいずれかです。それぞれの最小回数に1（今回の操作）を足した中で最小を選びます。
動作原理
ステップ1. dp[1] = 0から始め、残りは∞（未確定）にします。
ステップ2. 2からXまで小さい数から順に埋めます。dp[i]を計算するとき、dp[i-1]、dp[i/2]、dp[i/3]はすべて既に確定しています。
ステップ3. dp[X]が最終的な答えです。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(X) |
| 空間 | O(X) |
各iを一度だけ計算し、毎回定数個（最大3個）の候補を比較するだけなので、全体でO(X)です。
よくあるミス
- •インデックス0の扱い:
dp[1] = 0が基底条件です。インデックス0は未使用です。 - •割り算条件の漏れ: ÷2は偶数のとき、÷3は3の倍数のときだけ候補に入れます。
- •グリディで解く: 上の例のように「大きく割る優先」グリディには反例があります。必ずDPで全ての小さい数の最適解を保存してください。
AlgoNoteで直接確認しましょう
各マス dp[i] がどの操作（−1 / ÷2 / ÷3）で最小になるか、AlgoNoteの可視化で一段ずつ追ってみてください。開始の数を変えて、グリディがいつ罠にはまるか実験できます。