20171008_11844_쉬운 계단 수

#include <iostream> using namespace std; int main() {     int N=0;     int dp[101][10]={0};     int C=0;          cin >> N;     for(int i=1; i<10; i++) dp[1][i]=1;     for(int k=2; k<=N; k++)     {         for(int j=0; j<10; j++)         {             if(j==0) dp[k][0]=dp[k-1][1]%1000000000;             else if(j==9) dp[k][9]=dp[k-1][8]%1000000000;             else dp[k][j]=(dp[k-1][j-1]+dp[k-1][j+1])%1000000000;         }     }     for(int i=0; i<10; i++) C=(C + dp[N][i])%1000000000;          cout << C;     return 0;      }

dp[k][j]=j로 끝나는 k 자리 수의 개수 

** 계단수이므로 점화식은 본문처럼 !ㅎㅎ

for문 안에서 %1000000000을 안하면 마지막 C 구할 때 오버플로생기나?