1562 계단 수

백준 1562 계단 수 https://www.acmicpc.net/problem/1562

bitmask dp로 해결가능하다.

$DP[K][M][N]$ : M으로 시작하는 N자리 계단수(K는 숫자 정보 bit)

기본적인 점화식은 $DP[M][N] = DP[M-1][N-1] + DP[M+1][N-1] $

#include <cstdio> #define mod 1000000000 int N; int dp[1 << 10][10][101]; int main(){     scanf("%d", &N);     for (int n = 0; n < 10; n++)         dp[1 << n][n][1] = 1;        //n으로 시작하는 1자리수의 개수는 1개     for (int n = 2; n <= N; n++){         for (int m = 0; m < 10; m++){             for (int k = 1; k < 1024; k++){                 if (m == 9){                     dp[k | (1 << m)][m][n] += dp[k][m - 1][n - 1] % mod;                     dp[k | (1 << m)][m][n] %= mod;                 }                 else if (m != 0){                     dp[k | (1 << m)][m][n] += dp[k][m - 1][n - 1] % mod;                     dp[k | (1 << m)][m][n] %= mod;                 }             }             for (int t = 1; t < 1024; t++){                 if (m == 0){                     dp[t | (1 << m)][m][n] += dp[t][m + 1][n - 1] % mod;                     dp[t | (1 << m)][m][n] %= mod;                 }                 else if (m != 9){                     dp[t | (1 << m)][m][n] += dp[t][m + 1][n - 1] % mod;                     dp[t | (1 << m)][m][n] %= mod;                 }             }         }     }     int ans = 0;     for (int m = 1; m < 10; m++){         ans += dp[(1 << 10) - 1][m][N] % mod;         ans %= mod;     }     printf("%d\n", ans % mod);     return 0; } Colored by Color Scripter

cs