10844 - 쉬운 계단 수

//10844 - 쉬운 계단 수
 
#include <iostream>
using namespace std;
 
#define MOD 1000000000;
 
int N;
int cache[101][10];
 
void init()
{
    cin >> N;
    for(int i = 0; i<101; ++i)
        for(int j = 0; j<10; ++j)
            cache[i][j] = -1;
}
 
int dp(int n, int k)
{
    if(k < 0 || k > 9) return 0;
    if(n == 1) return 1;
 
    int& ret = cache[n][k];
    if(ret != -1)
        return ret;
    ret = (dp(n-1, k-1) + dp(n-1, k+1))%MOD;
    return ret;
}
 
int main()
{
    init();
    int ans = 0;
    for(int i = 1; i<10; ++i)
        ans = (ans + dp(N, i)) % MOD;
    cout << ans;
}

 

 

 

 

 

 

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

10844번: 쉬운 계단 수

 

 

 

 

 

 

쉬운 계단 수

DP입니다.

C(n, k) : 길이 n이고, k로 시작하는 계단 수의 개수

C(n, k) = C(n-1, k-1) + C(n-1, k+1)