계단 수 - 1562

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

 

 

 

 

 

 

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

1562번: 계단 수

 

 

 

 

 

 

계단 수

DP문제 입니다.

C(n, k, bt) : bt집합의 원소로 이루어진 k로 시작하는 n길이의 계단수의 개수

C(n, k, bt) = C(n-1, k-1, bt & ~(1<<k)) + C(n-1, k-1, bt) + C(n-1, k+1, bt & ~(1<<k)) + C(n-1, k+1, bt)

재귀 함수의 기저조건을 정의하는것이 까다로웠습니다.

그리고 비트마스크 사용할 때 연산자 우선순위에 주의해야 할거 같습니다!