Boj1562_계단수
백준 1562 계단수
비트 마스크 + dp
#include<iostream>
using namespace std;
#define MOD 1000000000
int n, dp[110][10][1024], ans; //길이가 n + 맨 뒤 숫자 + 0~9
int main() {
scanf("%d", &n);
for (int i = 1; i <= 9; i++) {
dp[1][i][1 << i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 1024; k++) {
if (j != 0) {
dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % MOD;
}
if (j != 9) {
dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % MOD;
}
}
}
}
for (int i = 0; i < 10; i++) {
ans = (ans + dp[n][i][1023]) % MOD;
}
printf("%d", ans);
}