https://beta.atcoder.jp/contests/abc099/tasks/abc099_c
前提知識
解説
https://beta.atcoder.jp/contests/abc099/submissions/2667784
メモ化再帰（動的計画法）で解く。
「f(cu) := cu円引き出すのに必要な最小の操作回数」
と定義して、メモ化再帰を行う。
状態数はcuが0～Nだけ取りうるのでO(N)
遷移であるが、1円の遷移は別に大丈夫。
6の累乗円の遷移はすぐにNを超えてしまうので、O(logN)くらい
9の累乗円の遷移も同様。
よって、遷移数はO(logN)となる。
これでO(NlogN)なので間に合う。
int N; //--------------------------------------------------------------------------------------------------- int memo[101010]; int f(int cu) { if (cu == 0) return 0; if (memo[cu]) return memo[cu]; int res = inf; // 1yen chmin(res, f(cu - 1) + 1); // 6yen int x = 6; while (x <= cu) { chmin(res, f(cu - x) + 1); x *= 6; } // 9yen x = 9; while (x <= cu) { chmin(res, f(cu - x) + 1); x *= 9; } return memo[cu] = res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; cout << f(N) << endl; }
