はまやんはまやんはまやん

hamayanhamayan's blog

硬貨の枚数2 [yukicoder No.636]

https://yukicoder.me/problems/no/636

前提知識

解法

https://yukicoder.me/submissions/231328

下から決める桁DPで解いていく。
メモ化再帰で書いていくと分かりやすい。
f(i, j) := [0,i]円+j円を支払うための最小枚数
当然f(N.length() - 1, 0)が答えになるわけだが、メモ化再帰の中身を詳しくコメントしていく。
「g[x] := x円を表現するための最小枚数」とする。

int f(int i, int j) { // =[0,i]円+j円を支払う最小枚数
    if (i < 0) {  iが負のときは全額支払い終わっているとき
        if(j == 0) return 0;  j==0なら追加で支払う必要は無いので0
        else return 1;    j==1なら1円分だけまだ支払いが残っているので1
    }
    if (0 <= memo[i][j]) return memo[i][j];  メモ化再帰用

    int res = inf;
    rep(d, 0, 10) {  d=[0,9]円分支払う事を考える
        int n = N[i] - '0' + j;  今の桁+jで支払うべき金額を出す

        int sm = g[d];  d円分支払うための枚数を出す
        if (d < n) sm += f(i - 1, 1) + g[10 + d - n];
  もしd < nなら足りないので上の桁で補ってもらうことにする
  その為、上の桁での最小支払枚数をえる時にj=1としておく。
  これで10円分+されるので10+dからnを引いたものがおつりになる。
  これを足して必要枚数とする。

        else sm += f(i - 1, 0) + g[d - n];  足りているならそのままおつりを計算して、上の桁での最小枚数を求める。

        chmin(res, sm);  10通り試してみて最小枚数を答える
    }

    return memo[i][j] = res;
}
string N;
//---------------------------------------------------------------------------------------------------
int g[11] = { 0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1 };
int memo[10101][2];
int f(int i, int j) { // =[0,i]円+j円を支払う最小枚数
    if (i < 0) {
        if(j == 0) return 0;
        else return 1;
    }
    if (0 <= memo[i][j]) return memo[i][j];

    int res = inf;
    rep(d, 0, 10) {
        int n = N[i] - '0' + j;

        int sm = g[d];
        if (d < n) sm += f(i - 1, 1) + g[10 + d - n];
        else sm += f(i - 1, 0) + g[d - n];

        chmin(res, sm);
    }

    return memo[i][j] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, 10101) rep(j, 0, 2) memo[i][j] = -1;
    cout << f(N.length() - 1, 0) << endl;
}