[C++] 백준 - 10844 : 쉬운 계단 수

문제 링크

10844번: 쉬운 계단 수

 

풀이 ) DP

  각 숫자는 0을 제외한 1부터 9까지의 숫자로 끝날 수 있다.

  0으로 끝나는 n자리 숫자는 1로 끝나는 n-1자리 숫자 + 0의 구조이고

  1로 끝나는 n자리 숫자는 0 또는 2로 끝나는 n-1자리 숫자 + 1의 구조이다.

  같은 방식으로 m으로 끝나는 n자리 숫자는 m-1 또는 m+1로 끝나는 n-1자리 숫자  + m이고

  마지막 9로 끝나는 경우 앞이 8로 끝나는 숫자 + 9의 구조이다.

  따라서 점화식은 다음과 같다.

  memo[i][j] = memo[i-1][1] ( j = 0 ), memo[i-1][j-1] + memo[i-1][j+1] ( 0 < j < 9 ), memo[i][8] ( j = 9 )

 

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[102][10] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, };

int main(void)
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; ++i){
        memo[i][0] = memo[i-1][1];
        for(int j = 1; j < 9; ++j)
            memo[i][j] = (memo[i-1][j-1]+memo[i-1][j+1]) % 1000000000;
        memo[i][9] = memo[i-1][8];
    }
    for(int i = 0; i < 10; ++i)
        ans = (ans + memo[n-1][i]) % 1000000000;
    printf("%d\n", ans);
    return 0;
}