[백준] 10844번 쉬운 계단 수 (python,c++)

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

10844번: 쉬운 계단 수

 

길이가 n인 계단수 총 개수를 f(n)이라 하자. f(n)에서 끝자리수는 이전 숫자에 영향을 받는다. 예컨데, 길이가 2이고 마지막 숫자가 1이라 했을때 이전숫자로 올 수 있는 것은 0,2이다. 이전 숫자이외의 숫자는 관심이 없다.

f(n,d)를 길이가 n이고 마지막 숫자가 d 인 계단 수 개수로 놓는다.

 

f(n,d)=f(n-1,d-1) + f(n-1,d+1)

 

위 점화식을 사용한다. 0은 +1만 가능하고 9는 -1만 가능하다는 것에 주의하여 문제를 풀어나간다.

 

 

---

SOLUTION CODE

# PYTHON

MOD = 1_000_000_000

# cahce[n][d]: 길이가 n,마지막 숫자가 d인 계단수 개수 ~= f(n,d)
cache = [[0]*10 for _ in range(101)] # n은 100개,마지막숫자 d는 0~9 총 10가지
for j in range(1,10):
    cache[1][j] = 1 # 초기값 세팅 f(1,d)

for i in range(2,101):
    for j in range(10):
        # cache[i][j] = cache[i-1][j-1]+cache[i-1][j+1]
        if j>0: # 0일땐 j-1 X
            cache[i][j] += cache[i-1][j-1]
            cache[i][j] %= MOD
        if j<9: # 9일땐 j+1 X
            cache[i][j] += cache[i-1][j+1]
            cache[i][j] %= MOD
            
ans=0
N = int(input())
for j in range(10):
    ans += cache[N][j]
    ans %= MOD
print(ans)

 

# C++

#include <iostream>
#include <cstdio>

using namespace std;

const int mod = 1e9;

int cache[101][10];

int bottomUp(int n){
    for (int i =1; i<10; i++) cache[1][i] = 1;
    
    for(int l=2;l<=n;l++){
        for(int d=0;d<10;d++){
            if(d==0){
                cache[l][d] = cache[l-1][d+1] % mod;
            }
            else if(d==9){
                cache[l][d] = cache[l-1][d-1] % mod;
            }
            else {
                cache[l][d] = (cache[l-1][d-1]+cache[l-1][d+1])%mod;
            }
        }
    }
    int sum=0;
    for(int i=0;i<10;i++){
        sum = (sum+cache[n][i])%mod;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout << bottomUp(n);
    return 0;
}