C++で整数nを0に減らすのに必要な最小操作回数を求めるプログラム

問題の概要

ある整数 n が与えられます。この n を 0 に減らすために、次の3種類の操作を任意の順序・回数で実行できます。

• 操作1：n を 1 減らす
• 操作2：n が偶数の場合、n を n / 2 減らす（結果として n は半分になる）
• 操作3：n が 3 の倍数の場合、n を 2 × (n / 3) 減らす（結果として n は 1/3 になる）

求めたいのは、n を 0 にするまでに必要な操作回数の最小値です。

入出力の例

入力が n = 16 の場合、出力は 5 になります。手順は以下の通りです。

• 16 は偶数なので、「n / 2 減らす」操作を4回繰り返すと 16 → 8 → 4 → 2 → 1 となります
• 最後に 1 を減らして 0 にします

合計 5 回の操作で 0 に到達でき、これが最小回数です。

解き方のアプローチ

この問題は、メモ化（キャッシュ）付きの深さ優先探索（DFS）で効率的に解けます。考え方の手順は次の通りです。

• 計算済みの結果を保存するマップ dp を定義する
• 関数 dfs() を定義し、引数 x を受け取る
• ret := x で初期化する
• x が dp に存在する場合は dp[x] を返す（再計算を避ける）
• x <= 0 の場合は x をそのまま返す
• x == 1 の場合は 1 を返す
• md2 := x mod 2、md3 := x mod 3 を求める
• ret := {ret, md2 + 1 + dfs((x − md2) / 2), md3 + 1 + dfs((x − md3) / 3)} の最小値とする
• dp[x] = ret を保存して返す
• main 関数から dfs(n) を呼び出し、その結果を返す

アルゴリズムのポイント

「n / 2 減らす」「2 × (n / 3) 減らす」という操作は、条件を満たすときに n をそれぞれ半分・1/3 にできる非常に強力な操作です。そこで各ステップでは、「余り（mod 2 または mod 3）のぶんだけ 1 を減らして割り切れる状態にしてから、一気に割る」という戦略を取り、そのコストを再帰的に比較します。さらに、一度計算した値を dp マップにキャッシュすることで同じ状態の再計算を防ぎ、高速に最小回数を求められます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> dp;

int dfs(int x){
    int ret = x;
    if(dp.count(x))
        return dp[x];
    if(x <= 0)
        return x;
    if(x == 1)
        return 1;
    int md2 = x % 2;
    int md3 = x % 3;
    ret = min({ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)});
    return dp[x] = ret;
}

int solve(int n) {
    return dfs(n);
}

int main(){
    int n = 16;
    cout << solve(n);
}

実行結果

入力：

16

出力：

5

計算量について

メモ化により、同じ値 x に対する計算は一度しか行われません。再帰の各段階で候補は高々2つに分岐し、深さはおおよそ log n に比例するため、全体の時間計算量・空間計算量は O(log² n) 程度に抑えられます。大きな n でも現実的な時間で答えを得られるのが、このアプローチの大きな利点です。