[Algorithm] Baekjoon 10844번 : 쉬운 계단 수

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

10844번: 쉬운 계단 수

#define MOD 1000000000
 
int dp[101][10] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i <= 9; ++i)
    {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            if (j == 0)
            {
                dp[i][0] = (dp[i][0] % MOD + dp[i - 1][1] % MOD) % MOD;
            }
            else if (j == 9)
            {
                dp[i][9] = (dp[i][9] % MOD + dp[i - 1][8] % MOD) % MOD;
            }
            else // 1 ~ 8
            {
                dp[i][j] = (dp[i][j] % MOD + dp[i - 1][j-1] % MOD) % MOD;
                dp[i][j] = (dp[i][j] % MOD + dp[i - 1][j+1] % MOD) % MOD;
            }
        }
    }
 
    int answer = 0;
 
    for (int i = 1; i <= 9; ++i)
    {
        answer = (answer % MOD + dp[n][i] % MOD) % MOD;
    }
 
    cout << answer;
}

 

전 문제랑 비슷하다. 제일 오른쪽자리수부터 dp값을 누적시키며 점점 큰자리수의 dp값을 업데이트시켜야 한다.

현재자릿수값이 8이라면 현재자릿수-1의 -1인 7과, +1인 9값을 가져와서 합산하면 된다.

단, 0일때는 -1값이 없기때문에 따로 예외로 해서 1값만 합산하게한다.

마찬가지로 9일때는 +1값이 없기 때문에 -1인 8값만 합산하게 한다.

이외에는 -1,+1값을 합산시켜서 dp테이블을 업데이트하면 된다.