문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

import sys

input = lambda: sys.stdin.readline().strip()

n = int(input())
arr = [[0 for _ in range(10)] for _ in range(100)]
arr[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(1, n):
  for j in range(10):
    if j == 0:
      arr[i][j + 1] = (arr[i][j + 1] + arr[i - 1][j]) % 1000000000
    elif j == 9:
      arr[i][j - 1] = (arr[i][j - 1] + arr[i - 1][j]) % 1000000000
    else:
      arr[i][j - 1] = (arr[i][j - 1] + arr[i - 1][j]) % 1000000000
      arr[i][j + 1] = (arr[i][j + 1] + arr[i - 1][j]) % 1000000000

print(sum(arr[n - 1]) % 1000000000)

백준 10844 쉬운 계단 수