18244번 변형 계단 수

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

아래의 문제를 변형한 문제이다

쉬운 계단 수 : https://www.acmicpc.net/problem/10844

dp[i][j][k] : 길이가 i이고, 끝자리가 j인 숫자. 단 k는 아래와 같다.

k=1 : 2번 감소된 상태

k=2 : 1번 감소된 상태

k=3 : 초기 상태

k=4 : 1번 증가된 상태

k=5 : 2번 증가된 상태

설명은 주석으로 대체

#include <bits/stdc++.h>
 
using namespace std; 
 
#define Max 102
#define Mod 1000000007
 
int dp[Max][Max][6], n, ans;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    
    // 한 자리 수
    for (int i = 0; i <= 9; i++) {
        dp[1][i][3] = 1;
    }
 
    scanf("%d", &n);
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j == 0) {
                // 감소(1에서 0으로 감소하는 경우밖에 없음)
 
                // 이미 1번 감소한 상태(=3차원 배열 인덱스가 2)에서는 2번 감소한 상태(=3차원 배열 인덱스가 1)로 가야한다.
                dp[i][0][1] += dp[i - 1][1][2] % Mod; 
                
                // 0번 감소한 상태(=3차원 배열 인덱스가 3)에서는 1번 감소한 상태(=3차원 배열 인덱스가 2)로 가야한다.
                // 또는
                // 0번 감소한 상태(=3차원 배열 인덱스가 4 = 1번 증가된 상태)에서는 1번 감소한 상태(=3차원 배열 인덱스가 2)로 가야한다.
                // 또는
                // 0번 감소한 상태(=3차원 배열 인덱스가 5 = 2번 증가된 상태)에서는 1번 감소한 상태(=3차원 배열 인덱스가 2)로 가야한다.
                dp[i][0][2] += (dp[i - 1][1][3] % Mod + dp[i - 1][1][4] % Mod + dp[i - 1][1][5] % Mod) % Mod;
            }
            else if (j == 9) {
                // 증가
 
                // 0번 증가된 상태(=3차원 배열 인덱스가 1 = 2번 감소된 상태)에서는 1번 증가된 상태(=3차원 배열 인덱스가 4)로 가야한다.
                // 또는
                // 0번 증가된 상태(=3차원 배열 인덱스가 2 = 1번 감소된 상태)에서는 1번 증가된 상태(=3차원 배열 인덱스가 4)로 가야한다.
                // 또는
                // 0번 증가된 상태(=3차원 배열 인덱스가 3 = 초기 상태)에서는 1번 증가된 상태(=3차원 배열 인덱스가 4)로 가야한다.
                dp[i][9][4] += (dp[i - 1][8][1] % Mod + dp[i - 1][8][2] % Mod + dp[i - 1][8][3] % Mod) %  Mod;
 
                // 이미 1번 증가된 상태(=3차원 배열 인덱스가 4)에서는 2번 증가된 상태(=3차원 배열 인덱스가 5)로 가야한다.
                dp[i][9][5] += dp[i - 1][8][4] % Mod;
            }
            else {
                // 감소(0번 또는 1번 또는 2번 증가된 상태에서 감소된 상태로 가야한다.)
                dp[i][j][1] += dp[i - 1][j + 1][2] % Mod; // 이미 1번 감소된 상태에서는 2번 감소된 상태(=3차원 배열 인덱스가 1)로 가야한다.
 
                // 3차원 배열 인덱스가 3, 4, 5에서는 1번 감소된 상태(=3차원 배열 인덱스가 2)로 가야한다.
                dp[i][j][2] += (dp[i - 1][j + 1][3] % Mod + dp[i - 1][j + 1][4] % Mod + dp[i - 1][j + 1][5] % Mod) % Mod;
 
 
                // 증가(0번 또는 1번 증가된 상태에서 1번 또는 2번 증가된 상태로 가야한다.)
                dp[i][j][4] += (dp[i - 1][j - 1][1] % Mod + dp[i - 1][j - 1][2] % Mod + dp[i - 1][j - 1][3] % Mod) % Mod;
                dp[i][j][5] += dp[i - 1][j - 1][4] % Mod;
            }
        }
    }
    
    for (int j = 0; j <= 9; j++) {
        for (int k = 1; k <= 5; k++) {
            ans = (ans % Mod + dp[n][j][k] % Mod) % Mod;
        }
    }
    
    printf("%d\n", ans % Mod);
 
    return 0;
}