BOJ 10844 쉬운 계단 수

https://www.acmicpc.net/problem/10844

 

- DP

- d[] : 길이가 n인 계단 수

- 예외처리 할 것이 늘어남!

 : 길이가 1일때

 : 길이 2이상일 때 - 모든 0과 9에 대하여

 

#include <cstdio>
int d[102][10];
long long int mod = 1000000000;
long long ans=0;
int main(){
  int n;
  scanf("%d", &n);

  for(int i=1; i<=9; i++)
    d[1][i]=1; //길이 1일 때

  for(int i=2; i<=n; i++){
    for(int j=0; j<=9; j++){
      d[i][j]=0; //초기화
      if(j-1>=0) d[i][j] = d[i][j] + d[i-1][j-1]; //9포함
      if(j+1<=9) d[i][j] = d[i][j] + d[i-1][j+1]; //1포함
      //1, 9를 제외하고는 if 두번 진행
      d[i][j] %= mod;
    }
  }

 //0부터 9까지 길이가 n이면서 마지막 수 i 모두 더한다.
  for(int i=0; i<=9; i++){
    ans = ans + d[n][i];
  }
  ans %= mod;

  printf("%lld", ans);
}