yukicoder - No.1085 桁和の桁和

問題リンク

解説

ある整数 Xの桁和を繰り返していくと、基本的には9で割った余りになる。ただし、9で割った余りが0の場合がやっかいで、


\begin{align}
\left\{
\begin{array}{ll}
(最終的な桁和) = 9 \ (X > 0) \\ \\
(最終的な桁和) = 0 \ (X = 0)
\end{array}
\right.
\end{align}

となる。ここまで分かれば、あとは簡単で、



dp[i][j][k] := i桁目までみたとき、9で割った余りがj 。
ただし、\\
0以外の数字がでていない\ \mathrm{if} : k == 0 \\

0以外の数字がでた\  \ \mathrm{if} : k == 1

遷移は簡単です。

提出コード

yukicoder.me