[algorithm] 백준 - 쉬운 계단 수



DP 문제이다.

 

이 문제의 특징은 모든 자리수의 차이가 1이 난다는 것이다.

 

그렇다면,

마지막 자릿수	다음 자릿수
0	1
1	0, 2
2	1, 3
...	...
9	8

로 이루어질 수 있다.

 

n을 자릿수라고 생각했을 때,

n = 2 일 때,
12 10
21 23
...
98

n = 3 일 때,
121 120 101
210 212 232 234
...
989 987

 

이것을 점화식으로 표현해보면,

dp[n][i] = dp[n - 1][i - 1] + dp[n - 1][i + 1]

로 계속 쌓아나가는 과정을 볼 수 있다.

 

코드로는

// 쉬운 계단 수
#include <iostream>
using namespace std;
int main(void){
    long long count, dp[101][10], total = 0;
    cin >> count;
    for(int i = 1; i < 10; i++){
        dp[1][i] = 1;
    }
    dp[1][0] = 0;
    for(int i = 2; i <= count; i++){
        for(int j = 0; j < 10; j++){
            if(j == 9){
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if(j == 0){
                dp[i][j] = dp[i - 1][j + 1];
            }
            else{
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])% 1000000000;
            }
        }
    }
    for(int i = 0; i < 10; i++){
        total = (total + dp[count][i])% 1000000000;
    }
    cout << total % 1000000000;
}