가지치기를 그리다가 규칙을 발견했다...
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)
smilegate