코드

N = int(input())

dp = [[0 for _ in range(10)] for _ in range(N+1)]

dp[1] = [0,1,1,1,1,1,1,1,1,1]


for i in range(2,N+1):
    for j in range(10):
        if j==0:
            dp[i][j] = dp[i-1][1]
        elif j==9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]


print(sum(dp[-1])%1000000000)

풀이

• 1의 자리수부터 자리수가 높아지면서 올 수 있는 경우의 수를 추가하는 방식.