[백준/DP] 10844 쉬운 계단 수 (Python, 파이썬)

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

10844번: 쉬운 계단 수

 

 

문제의 조건

- 인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다.

- 예 : 45656

- 길이가 N인 계단 수의 개수를 구하는 문제

 

D[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수

D[i][j] = D[i-1][j-1] + D[i-1][j+1] ( 1<= j <= 8 )

=> 근접한 수만 가능하므로 j-1, j+1 두 가지 경우

 

초기화 : D[1][0] = 0, D[1][1]  = D[1][2] = ... = D[1][9] = 1

정답 : D[n][0] + ... + D[n][9]

 

mod = 1000000000 # 나눌 수
d = [[0] * 10 for _ in range(101)] # n <= 100 
n = int(input())

for i in range(1, 10): # 초기화
    d[1][i] = 1 

for i in range(2, n+1):
    for j in range(10):
        d[i][j] = 0
        if j-1 >= 0:
            d[i][j] += d[i-1][j-1]

        if j+1 <= 9:
            d[i][j] += d[i-1][j+1]
        d[i][j] %= mod

ans = 0
for i in range(10):
    ans += d[n][i]
print(ans%mod)