2688 줄어들지 않아

백준 2688 줄어들지 않아 https://www.acmicpc.net/problem/2688

0001, 0004, 1234 들은 줄어들지 않는 숫자들이다.
자릿수 N이 주어졌을 때 줄어들지 않는 숫자들의 갯수를 구하는 문제이다.

$D[N][K]$ : 마지막 숫자가 K인 자릿수 N개의 줄어들지 않는 숫자들의 갯수

D[3][2]를 예로 들어보자.
경우는 {0,0,2}, {0,1,2}, {1,1,2}, {0,2,2}, {1,2,2}, {2,2,2}가 있겠다.
마지막수 2를 제외하고 앞의 두자리만 보면 {0,0}, {0,1}, {1,1}, {0,2}, {1,2}, {2,2}
이숫자들은 D[2][0], D[2][1], D[2][2]임을 알 수 있다.

즉, D[3][2] = D[2][0] + D[2][1] + D[2][2]
                = D[3][1] + D[2][2]

$D[N][K] = \sum_{0}^{K-1}D[N][K]+D[N-1][K]$

∴ $D[N][K] = D[N][K-1]+D[N-1][K]$

#include <cstdio> #include <cmath> long long dp[65][10]; int main(){     int T;     scanf("%d", &T);     for (int n = 0; n <= 9; n++){         dp[1][n] = 1;         dp[2][n] = n + 1;     }     while (T--){         int N;         scanf("%d", &N);         if (dp[N][0] == 0){             for (int n = 3; n <= N; n++){                 dp[n][0] = 1;                 for (int k = 1; k <= 9; k++)                     dp[n][k] = dp[n - 1][k] + dp[n][k - 1];             }         }         long long ans = 0;         for (int n = 0; n <= 9; n++)             ans += dp[N][n];         printf("%lld\n", ans);     }     return 0; } Colored by Color Scripter

cs