백준 10844 쉬운 계단 수 / C++

문제 : 10844

풀이 point

계단 수는 인접한 모든 자리의 차이가 1이다. 예시를 들어보면 3의 경우에는 2의 뒤 또는 4의 앞에 올수 있다. 4또한 3의 뒤 or 5의 앞에 올 수 있다.

단, 0이나 9는 예외이다. 0은 1앞에만 올 수 있다. 9는 8의 뒤에만 올 수 있다.

그렇다면 길이가 N일때 3이 올 수 있는 경우의 수는 길이가 N-1일때 2의 뒤 or 4의 앞이다.

풀이 방법

dp배열을 2차원으로 만든 후 0과 9를 예외로 처리한다.(0은 1앞에만, 9는 8뒤에만)
나머지 숫자들은 길이가 N-1일때 n-1의 뒤 또는 n+1의 앞에 올 수 있으므로 두 경우의 수를 합한다.

코드

//백준 10844, 쉬운 계단 수

#include <iostream>
#define mod 1'000'000'000 
using ll = long long;

ll dp[101][10];

int main (){

    int N;
    std::cin >> N;

    
    for(int j{1}; j<10; ++j){
        dp[1][j] = 1;
    }
    

    for(int i{2}; i<=N; ++i){
        for(int j{0}; j<10; ++j){
            if(j == 0) dp[i][j] = dp[i-1][j+1]%mod;
            else if(j == 9) dp[i][j] = dp[i-1][j-1]%mod;
            else{
                dp[i][j] = dp[i-1][j-1]%mod + dp[i-1][j+1]%mod;
            }
        }
    }
    ll sum = 0;
    for(int i{0}; i<10; ++i){
        sum = sum%mod + dp[N][i]%mod;
    }

    std::cout << sum%mod;

    return 0;
}