실버1 : 동적계획법 문제이다.
생각
dp[i][j] = i개의 자리수를 갖는 계단수중 끝자리가 j인 것의 개수
i == 1
1 2 3 4 5 6 7 8 9
i == 2
01 12 23 34 45 56 67 78 89
10 21 32 43 54 65 76 87 98
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll div_n = 1000000000;
int N = 0;
int dp[101][101] = {0,};
int main(){
cin >> N;
for (int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= 9; j++) {
if (j == 0) {
dp[i][j] = dp[i-1][j+1];
continue;
}
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % div_n;
}
}
ll ans = 0;
for (int i = 0; i <= 9; i++) {
ans += dp[N][i];
ans %= div_n;
}
cout << ans << '\n';
return 0;
}