DP_백준_쉬운 계단 수_10844

마지막에 무슨 수가 들어 가는지를 모른다. 따라서 길이가 N이고 마지막 상태를 나타내는 L로 2차원 배열을 사용한다.

1. 정의 : dp[N][L] : 길이가 N이고 마지막 숫자가 L일때 총 계단 수의 갯수

2. 점화식 : dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1] (1<=L<=8)

              dp[N][0] = dp[N-1][1]

              dp[N][9] = dp[N-1][8]

3. 초기화 : 코드 참조

시간 복잡도는 O(N)이다.

#include <iostream>
using namespace std;
 
int main() {
    int num;
    long long d[101][10];
    for (int i = 1; i <= 9; i++) {
        d[1][i] = 1;
    }
    d[1][0] = 0;
 
    cin >> num;
    for (int i = 2; i <= num; i++) {
        for (int k = 0; k <= 9; k++) {
            if (k == 0) {
                d[i][0] = d[i - 1][1];
            }
            if (k == 9) {
                d[i][9] = d[i - 1][8];
            }
            if (k >= 1 && k <= 8) {
                d[i][k] = (d[i - 1][k - 1] + d[i - 1][k + 1]) % 1000000000;
            }
        }
    }
 
    long long sum = 0;
    for (int i = 0; i <= 9; i++) {
        sum += d[num][i];
        sum %= 1000000000;
    }
    cout << sum << endl;
}