백준 10844 - 쉬운 계단 수 [파이썬]

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

10844번: 쉬운 계단 수

 

풀이 과정

D[n][k] => 마지막이 k로 끝나는 n자리 계단수의 개수라고 하자

모든 인접한 자리의 차이가 1이어야 한다는 점을 고려하면 다음과 같은 점화식을 생각할 수 있다

 

D[n][0] = D[n-1][1]

D[n][k] = D[n-1][k-1] + D[n-1][k+1] (1 <= k <= 8)

D[n][9] = D[n-1][8]

 

이를 통해 문제를 해결할 수 있다

 

 

소스 코드

N = int(input())
d = [0, [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

for i in range(2, N+1):
    d.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
    d[i][0] = d[i-1][1] % 1000000000
    d[i][9] = d[i-1][8] % 1000000000
    for k in range(1, 9):
        d[i][k] = d[i-1][k-1]+ d[i-1][k+1]
        d[i][k] %= 1000000000

print(sum(d[N]) % 1000000000)