下の桁から順に見ていく. \(i\) 桁目の数字を \(D_i\) とする

\(i\) 桁目まで見たときにより上位の紙幣を使わないで合計で使う紙幣の枚数の最小値を \(A_i\), より上位の紙幣を使って合計で使う紙幣の命数の最小値を \(B_i\) とする. このとき,

\[\begin{align} A_i &= \min \{ A_{i-1} + D_i, B_{i-1} + D_i + 1 \} \\ B_i &= \min \{ A_{i-1} + (10 - D_i), B_{i-1} + (10 - (D_i + 1)) \} \end{align}\]

となる. これを DP で計算する.

\(N\) の桁数を \(m\) とすると, 答えは \(\min \{ A(m), B(m) + 1 \}\) である.