Strange Bank [AtCoder Beginner Contest 099 C]

atcoder.jp

この問題は解説を読んでも全く理解できなかったので、以下の解説サイトを参考に、やったこともないDPで解いてみることにしました。

nomikura.hatenablog.com

DPはやったこともないと書きましたが、一応、おぼろげには理解しているつもりです。累積和とか、フィボナッチ数列とか、そのあたりですね。

まず、int型配列 dp を作成し、dp[i] を「i 円を引き出すときの最小操作回数」とします。i は最大で 100000 なので、dp の長さもそれを超えるように定義します。

int[] dp = new int[100005];

dp を遷移（？）させていくためには初期値が必要です。よって初期値を定義します。

dp[0] = 0;　//0円引き出すときの最小操作回数は0回

また、1回に引き出せる金額（1, 6^1, 9^1, 6^2, 9^2......）も配列に入れておきます。

int[] ar = {1,6,9,36,81,216,729,1296,6561,7776,46656,59049};

N は最大で 100000 なので、1回に引き出せる金額はこれらの12個しかありません。ループで求めることもできますが、個数が少ないので手動で配列に入れてしまいました。

さて、これで準備が整ったので、いよいよ動的計画法を使って dp を遷移させていきます。

for (int i=1; i<=n; i++) {

	int min = Integer.MAX_VALUE;
	for (int j=0; j<ar.length; j++) {
		if (i >= ar[j]) {
			min = Math.min(min, Math.min(dp[i-1]+1, dp[i-ar[j]]+1));
		}
	}
	dp[i] = min;
	
}

解説サイトとループ内部の処理が異なっていますが、これは自分の頭で理解できる程度まで記述のレベルを下げたからです。

dp[i] = Math.min(dp[i-1]+1, dp[i-ar[j]]+1) 　※ただし、i>= ar[j]

という遷移式で遷移していきます。遷移式の意味は、

・i円の最小操作回数 = min(i-1円の最小操作回数+1, i-ar[j]円の最小操作回数+1)

です。

イメージとしては、所持金 i-ar[j] 円の状態からお金を引き出して i 円にするには、1回の操作で済む、といった感じでしょうか。今回書いたプログラムでは ar[j] の値を 1,6,9......59049 と全て試しながら、最小値を更新していって、最終的な最小値を「i 円を引き出すときの最小操作回数」として dp[i] に代入しています。

このような手順で dp[i] を1からNまで求めていって、遷移が終わった後 dp[N] に入っている値が答えになります。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int[] ar = {1,6,9,36,81,216,729,1296,6561,7776,46656,59049};
		
		int[] dp = new int[100005];
		dp[0] = 0;
		
		for (int i=1; i<=n; i++) {
			
			int min = Integer.MAX_VALUE;
			for (int j=0; j<ar.length; j++) {
				if (i >= ar[j]) {
					min = Math.min(min, Math.min(dp[i-1]+1, dp[i-ar[j]]+1));
				}
			}
			dp[i] = min;
			
		}
		
		System.out.println(dp[n]);
	}
}