쉬운 계단 수 #10844

문제

45656이란 수를 보자.

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

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

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍

---

import sys
alist = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
temp = [0] * 10
for _ in range(int(sys.stdin.readline())-1):
    for i in range(10):
        if i == 0:
            temp[i] = alist[i + 1]
        elif i == 9:
            temp[i] = alist[i - 1]
        else:
            temp[i] = alist[i - 1] + alist[i + 1]
    alist = temp.copy()
print(sum(alist)% 1000000000)