백준 10844. 쉬운 계단 수

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

10844번: 쉬운 계단 수

'''
길이가 N인 계단 수 몇개?
1<=N<=100
인접한 모든 자리의 차이가 1
'''
N = int(input())
dp = [[0]*10 for _ in range(N+1)] # [자리수(0~9) | 끝에 오는 수]

for i in range(10):  # 길이가 1이고 마지막 숫자가 i인 계단 수가 1개 있음 = 한자리 숫자는 모두 계단 수
    if i == 0: # 0으로 시작하는 수는 안 셈! continue로 인해 dp[1][i] = 1가 실행되지 않고 다음 i로 넘어감
        continue
    dp[1][i] = 1

# 끝에 오는 수가 0 / 1-8 / 9 세 가지로 나눠야 함

for i in range(2, N+1): # i는 길이(N)
    for j in range(10): # j는 끝에 오는 수
        if j == 0: # 끝에 오는 수가 0이면 앞에 1밖에 못 옴
            dp[i][j] = dp[i-1][j+1] # 현재 길이(i)의 끝에 오는 수가 0이면 ? 이전 길이(i-1)의 1로 끝나는 수를 넣음
        elif j == 9: # 끝에 오는 수가 9면 앞에 8밖에 못 옴
            dp[i][j] = dp[i-1][j-1] # 현재 길이(i)의 끝에 오는 수가 9이면 ? 이전 길이(i-1)의 8로 끝나는 수를 넣음
        else: # 끝에 오는 수가 1~8이면 앞에 +1, -1 2개 올 수 있음
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] # 현재 길이(i)의 끝에 오는 수가 1~8이면 ? 이전 길이(i-1)의 앞수와 뒷수를 합해서 넣음

print(sum(dp[-1]) % 1000000000) # dp의 가장 맨끝(끝까지 누적합 한 결과)