문제

입력 , 출력

import sys
input = sys.stdin.readline
n = int(input())
res = [[0] * 10 for i in range(n+1)]
res[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n+1):
    res[i][0] = res[i-1][1]
    res[i][9] = res[i-1][8]
    for j in range(1, 9):
        res[i][j] = res[i-1][j-1]+res[i-1][j+1]
print(sum(res[n]) % 1000000000)

설명

1자리수 계단수는 1,2,3,4,5,6,7,8,9 총 9 개가 있다
0으로 시작하는 수는 없기에 맨 앞자리가 0 인경우 , 즉 01 , 012 등은
계단수가 아니다.
간단하게 규칙을 보면 배열에서 dp[i][n] , i는 자리수 n은 0~9까지
dp[i][n] = dp[i-1][n-1] + dp[i-1][n+1] 이라는 규칙이 나온다.
하지만 n = 0 , n = 9 인 경우는 규칙이 다르다 그림을보면
n = 0 은 dp[i-1][n+1] , n =9 는 dp[i-1][n-1]
라는 규칙이 나온다.

이미지 설명

후기

2차원 배열에서 dp를 사용하는 경우를 생각하지도 못했다...
결국 답을 보고 이해한 후 코드를 보지않고 구현을 했다
아직 점화식을 구하는법이 익숙하지 않은듯 하다..
DP문제는 결국 점화식을 구하는건데 많은 유형을 풀어봐야 할듯?