BOJ 10844 · 쉬운 계단 수

알고리즘 분류 : 다이나믹 프로그래밍  

DP를 통해 계단 수의 총개수를 구하는 문제다.

• D[N][M] : M으로 끝나는 N자리 계단 수의 총개수
• D[1][1] = 1, D[1][2] = 1, ‥‥ , D[1][9] = 1 (한 자릿수)
• D[N][0] = D[N-1][1] : 0으로 끝나는 N자리 계단 수의 총개수
• D[N][1] = D[N-1][0] + D[N-1][2] : 1로 끝나는 N자리 계단 수의 총개수
• ‥‥
• D[N][8] = D[N-1][7] + D[N-1][9]
• D[N][9] = D[N-1][8]

---

C++ 소스코드

#include <cstdio>

const int mod = 1000000000;
int n;
long long ans, d[101][10];

void solve() {
    for (int i=1; i<10; i++) d[1][i] = 1;
    for (int i=2; i<=n; i++) {
        for (int j=0; j<10; j++) {
            if (j > 0) d[i][j] += d[i-1][j-1];
            if (j < 9) d[i][j] += d[i-1][j+1];
            d[i][j] %= mod;
        }
    }
    for (int i=0; i<10; i++) ans += d[n][i];
    printf("%lld\n", ans%mod);
}

int main() {
    scanf("%d", &n);
    solve();
    return 0;
}

---

Python 3 소스코드

n = int(input())
d = [[0]*10 for _ in range(n+1)]
ans, mod = 0, 1000000000

def solve():
    for i in range(1, 10):
        d[1][i] = 1
    for i in range(2, n+1):
        for j in range(0, 10):
            if j > 0:
                d[i][j] += d[i-1][j-1]
            if j < 9:
                d[i][j] += d[i-1][j+1]
            d[i][j] %= mod

solve()
print(sum(d[n])%mod)

---

참고

• 백준 온라인 저지 : BOJ 10844