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

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

10844번: 쉬운 계단 수

n = int(input())

easy_stairs = [[0 for i in range(10)] for j in range(101)]

for i in range(1,10):
    easy_stairs[1][i] = 1


    
for i in range(2,n+1):
    for k in range(10):
        if k == 0:
            easy_stairs[i][k]= easy_stairs[i-1][1]

        elif k==9:
            easy_stairs[i][k]= easy_stairs[i-1][8]
        
        else:
            easy_stairs[i][k] = easy_stairs[i-1][k-1] + easy_stairs[i-1][k+1]
print(sum(easy_stairs[n])% 1000000000)

 

이문제는.....

그냥 생각하고 문제를 이해하는 과정에서 힘들었다.

 

점화식을 생각해야했고 메모지에시션을 생각하면 된다.

 

이전에 저장해둔 마지막자리에 해당하는 수를 기록해두고 다음에 올 수만 고려하면서 해결하면 되는 문제이다