[BOJ] 백준 10844 쉬운 계단 수

문제 링크

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

풀이

(마지막 수 $\pm$ 1)의 방향으로 전개합니다.

길이가 $n$이 될 때까지 전개 가능하면 1을 리턴합니다.

 

0으로 시작하는 수는 없다는 것에 주의하세요.

해당 처리를 line 16 ~ 22에서 했습니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll d[111][10];
const int MOD = 1'000'000'000;

ll go(int l, int last) {
    if (last < 0 || last > 9) return 0;
    if (l == n) return 1;

    ll &ret = d[l][last];
    if (ret != -1) return ret;
    ret = 0;
    if (l == 0 && last == 0) {
        for (int i = 1; i < 10; i++) {
            ret += go(l + 1, i);
            ret %= MOD;
        }
        return ret;
    }
    ret = go(l + 1, last + 1) + go(l + 1, last - 1);
    ret %= MOD;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(d, -1, sizeof(d));
    cin >> n;
    cout << go(0, 0);
}