[Python]동적계획법 백준 10844

   문제

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

이번계단을 기준으로 이전계단의 될수있는 값들을 합친다.

예를 들면 이번계단이 5라면 이전계단은 4,6이고 4,6까지의 오는 계단의 합이 이번계단이 

5일때 계단의 합이 된다는것을 알수있다.

하지만 0과 9에서는 1,8로 이전계단이 한개밖에 없다 이부분은 따로 처리해주어야한다.

코드를 보면 쉽게 이해 할수 있을것이다.

n=int(input())
 
result=[[1 for _ in range(10)] for _ in range(n)]#n번째계단이 0~9일때
result[0][0]=0#0부터 시작할수 없다.
for i in range(1,n):
    for j in range(10):#처음을 제외하면 0~9까지 가능하다
        if j==0:#이번계단이 0일때 이전계단이 될수잇는건 1밖에없다.
            result[i][j]=result[i-1][j+1]%1000000000
        elif j==9:##이번계단이 9일때 8밖에없다.
            result[i][j]=result[i-1][j-1]%1000000000
        else:#나머지경우에는 두가지 j-1 j+1 경우에서 올수있다.
            result[i][j]=result[i-1][j-1]+result[i-1][j+1]%1000000000
 
 
print(sum(result[n-1])%1000000000)