BOJ 10844번 쉬운 계단 수

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/10844/10844/%EC%86%8C%EC%8A%A4.cpp

 

언제쯤 이런 문제를 쉽게 풀 수 있을까

설명은 코드에 적어놓았다.

#include <iostream>
#include <cstring>
using namespace std;
#define MOD 1000000000
int dp[10][101];
 
// start_num : 현재 숫자
// len : 확인해야할 남은 자릿수
int dfs(int start_num, int len) {
// 0 미만 9 초과의 범위는 계산하지 않는다.
    if (start_num < 0 || start_num > 9) return 0;
 
// 이미 계산된 수는 더이상 계산할 필요 없으므로 그대로 가져다쓴다.
    if (dp[start_num][len] != -1) return dp[start_num][len];
 
// 현재 dp 가 가져야 할 값은
// 현재 숫자에서 -1,+1 을 한 재귀형식을 더한 값이다.
    dp[start_num][len] = (dfs(start_num - 1, len - 1) + dfs(start_num + 1, len - 1)) % MOD;
    return dp[start_num][len];
}
 
int main() {
    ios::sync_with_stdio(false);
 
    int N, total = 0;
    cin >> N;
 
    memset(dp, -1, sizeof(dp));
// 1자리수는 기본적으로 1가지밖에 없다.
    for (int i = 0; i <= 9; i++) dp[i][1] = 1;
 
// 0부터 시작하면 안되므로 1부터 시작한다.
// 이때 시작의 의미는 첫번째 자리숫자를 의미.
    for (int i = 1; i <= 9; i++) {
        total += dfs(i, N);
        total %= MOD;
    }
    
    cout << total;
    return 0;
}