BOJ - 쉬운 계단수(10844)

실버1 : 동적계획법 문제이다.

생각

dp[i][j] = i개의 자리수를 갖는 계단수중 끝자리가 j인 것의 개수

i == 1

1 2 3 4 5 6 7 8 9

i == 2

01 12 23 34 45 56 67 78 89

10 21 32 43 54 65 76 87 98

Code

//
//  main.cpp
//  algorithm_prac
//
//  Created by 최완식 on 2021/04/05.
//
 
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll div_n = 1000000000;
int N = 0;
int dp[101][101] = {0,};
 
int main(){
    cin >> N;
    for (int i = 1; i < 10; i++) {
        dp[1][i] = 1;
    }
    
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j == 0) {
                dp[i][j] = dp[i-1][j+1];
                continue;
            }
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % div_n;
        }
    }
    
    ll ans = 0;
    for (int i = 0; i <= 9; i++) {
        ans += dp[N][i];
        ans %= div_n;
    }
    
    cout << ans << '\n';
    
    return 0;
}
 

Reference

• 백준(10844번) - 쉬운 계단수