문제링크 : https://www.acmicpc.net/problem/10844
dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1]
#include<bits/stdc++.h>
using namespace std;
#define mine
const int MOD = 1000000000;
int N;
int dp[11][101];
int stairNum(){
for(int i=1; i<=9; i++){
dp[i][1] = 1;
}
for(int i=2; i<=N; i++){
dp[10][i] = 0 ;
for(int j=0; j<=9; j++){
if(j == 0) dp[j][i] = dp[j+1][i-1];
else dp[j][i] = (dp[j-1][i-1] + dp[j+1][i-1])%MOD;
}
}
int ret = 0;
for(int i=0; i<=9; i++){
//// 여기도 함부러 += 하면서 %쓰면 틀린다.
ret = (ret +dp[i][N]) %MOD;
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
cin >> N;
int res = 0;
memset(dp, 0, sizeof(dp));
cout<<stairNum()<<endl;
return 0;
}
이 문제는 해결하지 못하여 다른 사람의 블로그를 보았다. 여기서 0일때와 9일때의 특수조건을 주어서 문제를 쉽게 해결한 것을 보며 자유롭게 dp를 풀수 있도록 나아가야겠다.