C++で解く！コインを払ってNに到達するための最小操作回数を求める方法

問題の概要

5つの整数 N, A, B, C, D が与えられます。数値を0から開始し、目標値Nまで到達させることがゴールです。数値は以下の操作を、それぞれ決められた枚数のコインを支払うことで変更できます。

• 数値を2倍する：A枚のコインが必要
• 数値を3倍する：B枚のコインが必要
• 数値を5倍する：C枚のコインが必要
• 数値を1増やす、または1減らす：D枚のコインが必要

これらの操作は何回でも、好きな順序で実行できます。Nに到達するために必要な最小のコイン枚数を求めましょう。

入力例と出力例

例えば、入力が N = 11、A = 1、B = 2、C = 2、D = 8 の場合、出力は 19 になります。初期状態では x = 0 であり、次の手順で目標に到達できます。

• 8枚払って x を1増やす（x = 1）
• 1枚払って x を2倍する（x = 2）
• 2枚払って x を5倍する（x = 10）
• 8枚払って x を1増やす（x = 11）

合計コイン枚数は 8 + 1 + 2 + 8 = 19枚 となり、これが最適な手順です。

解法のアプローチ

この問題は、目標値Nから逆算して考えることで効率的に解けます。0から順に値を増やしていく代わりに、N側から「2で割る」「3で割る」「5で割る」操作を考え、割り切れなかった剰余分は「±1」の操作で調整します。メモ化再帰を使うことで、同じ値に対する計算を繰り返さずに済み、高速に答えを求められます。

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

整数型のキーと値を持つマップ f を用意する（メモ化用）
整数型のキーと真偽値を持つマップ vis を用意する（計算済みフラグ用）
関数 calc(n) を定義する:
n が 0 の場合:
    0 を返す
n がすでに計算済みの場合:
    f[n] を返す
vis[n] := 1 とする
res := calc(n / 2) + (n mod 2) * d + a
n mod 2 が 0 でない場合:
    res := res と calc(n / 2 + 1) + (2 - n mod 2) * d + a の小さい方
res := res と calc(n / 3) + (n mod 3) * d + b の小さい方
n mod 3 が 0 でない場合:
    res := res と calc(n / 3 + 1) + (3 - n mod 3) * d + b の小さい方
res := res と calc(n / 5) + (n mod 5) * d + c の小さい方
n mod 5 が 0 でない場合:
    res := res と calc(n / 5 + 1) + (5 - n mod 5) * d + c の小さい方
(res - 1) / n + 1 > d の場合（1ずつ増やすほうが安い場合）:
    res := n * d
f[n] := res として返す
main 関数で a, b, c, d を設定し、calc(n) を呼び出す

C++実装例

それでは、実際の実装を見ていきましょう。以下のコードで動作を確認できます。

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
map<long, long> f;
map<long, bool> vis;

long calc(long n){
    if (!n)
        return 0;
    if (vis.find(n) != vis.end())
        return f[n];
    vis[n] = 1;
    long res = calc(n / 2) + n % 2 * d + a;
    if (n % 2)
        res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
    res = min(res, calc(n / 3) + n % 3 * d + b);
    if (n % 3)
        res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
    res = min(res, calc(n / 5) + n % 5 * d + c);
    if (n % 5)
        res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
    if ((res - 1) / n + 1 > d)
        res = n * d;
    return f[n] = res;
}
int solve(int N, int A, int B, int C, int D){
    a = A;
    b = B;
    c = C;
    d = D;
    return calc(N);
}
int main(){
    int N = 11;
    int A = 1;
    int B = 2;
    int C = 2;
    int D = 8;
    cout << solve(N, A, B, C, D) << endl;
}

このコードでは、calc 関数がメモ化再帰によって各値の最小コストを計算します。n を2・3・5で割った商と剰余に着目し、剰余分を1増減で埋めるパターンと、商を1つ切り上げてから不足分を埋めるパターンの両方を比較します。最後に「1ずつ増やして合計 n × d かかる」場合と比べ、より安い方を採用することで答えが得られます。

入力

11, 1, 2, 2, 8

出力

19