BOJ 18244 : 변형 계단 수

은근 좋은 문제이다.

 

이 문제는 DP로 풀 수 있다.

 

dp[i][j][k] = (i번째 자릿수에서 수가 j이고 현재 움직인 상태가 k일 때 (k=1,2,3,4,5) );

 

여기서 k의 상태는 3일때를 기준으로 하여 감소하면 내려간 것, 증가하면 올라간 것으로 판단해준다.

 

j = 1, 9일때는 증가 또는 감소만 하므로 예외 처리를 해주자.

 

 

#include <bits/stdc++.h>
#define MEM 105
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
ll dp[MEM][MEM][MEM];
ll n,ans;
int main()
{
    sanic;
    cin >> n;
    for(int i=0; i<=9; i++)
        dp[1][i][3] = 1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<=9; j++){
            if(!j){
                dp[i][j][1] += dp[i-1][j+1][2]%MOD;
                dp[i][j][2] += (dp[i-1][j+1][3]+dp[i-1][j+1][4]+dp[i-1][j+1][5])%MOD;
            }
            else if(j==9){
                dp[i][j][5] += dp[i-1][j-1][4]%MOD;
                dp[i][j][4] += (dp[i-1][j-1][3]+dp[i-1][j-1][2]+dp[i-1][j-1][1])%MOD;
            }
            else{
                dp[i][j][1] += dp[i-1][j+1][2]%MOD;
                dp[i][j][2] += (dp[i-1][j+1][3]+dp[i-1][j+1][4]+dp[i-1][j+1][5])%MOD;
                dp[i][j][5] += dp[i-1][j-1][4]%MOD;
                dp[i][j][4] += (dp[i-1][j-1][3]+dp[i-1][j-1][2]+dp[i-1][j-1][1])%MOD;
            }
        }
    }
    for(int i=0; i<=9; i++)
        for(int j=1; j<=5; j++){
            ans =(ans%MOD+dp[n][i][j]%MOD);
            ans %= MOD;
        }
    cout << ans%MOD;
}