[백준] 10844. 쉬운 계단 수 python

[백준] 10844번 쉬운 계단 수

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

풀이과정

    0 1 2 3 4 5 6 7 8 9
1자리     0 1 1 1 1 1 1 1 1 1
2자리    1 1 2 2 2 2 2 2 2 1
3자리    1 3 3 4 4 4 4 4 3 2

n자리수로 만들 수 있는 계단 수들은 위와 같다.
2자리수일 때, 0을 끝자리로 만들 수 있는 수는 10 한가지이다. 1을 끝자리로 만들 수 있는 수는 21 한가지, 2를 끝자리로 만들 수 있는 수는 12 32 두가지이다. 이런 방법으로 계속 진행하면, 규칙을 발견할 수 있다. 그 규칙은 구하고자 하는 값은 V모양으로 더한 값이라는 것이다. . 어떻게 표현하즤

    0   1  2  3 4 5 6 7 8 9
1자리     0   1  1  1 1 1 1 1 1 1
2자리    (1) 1 (2) 2 2 2 2 2 2 1
3자리    1  <3>  3 4 4 4 4 4 3 2

() + () = <> 라는 뜻!!!!
이유는 쉽게 생각하자면 3자리 수 중 끝자리를 2로 하여 만들 수 있는 수는 앞 자리 수가 1과 3이여야하고, 그 앞은 또 끝자리가 1인 두자릿수, 끝자리가 3인 두자릿수와 같기 때문이다

소스코드

import sys
input = sys.stdin

n = int(input.readline().strip())
# dp 초기화
dp = [[1] * 10 for _ in range(n+1)]
dp[1][0] = 0 #1자릿수 중 0으로 만들 수 있는 수는 없으므로

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

print(sum(dp[n]) % 1000000000)
exit()