[알고리즘/백준] 10844: 쉬운 계단 수(python)

가지치기를 그리다가 규칙을 발견했다...
1차원으로는 도저히 불가능해서 2차원으로 했다.

       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

자세히 보면 규칙이 보인다. 0과 9를 제외하고는 바로 위 양쪽 대각선의 두 수를 합친게 현재 갯수가 된다. 0과 9는 각각 1과 8만 오는게 가능하다.

0이면
dp[i][j] = dp[i-1][j+1]

9면
dp[i][j] = dp[i-1][j-1]

나머지
dp[i][j] = dp[i-1][j-1] + dp[i+1][j+1]

N = int(input())
dp = list([0] * 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][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)