백준_10844_쉬운 계단 수(DP)

n = int(input())

dp = [[0]*10 for _ in range(n)]

for i in range(1, 10):
    dp[0][i] = 1

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

print(sum(dp[n-1]) % 1000000000)

우선 한 자릿수인 계단 수의 경우는 0으로 시작하는 수는 계단 수가 아니므로 1~9까지 총 9개이다.

두번 째 자릿수 부터 Dp 값을 구하면 되는데 0과 9의 경우는 각각 1과 8에서 오는 경우 밖에 없다.

따라서 0과 9인 경우는 그냥 1에서 오는 경우와 8에서 오는 경우에 값을 저장시키고 나머지 수는 그 수에대해 이전 자릿 값의 -1, +1인 수에 대하여 값을 가지고 와서 대해준다.

마지막에 마지막 자릿 수에 대해 다 더해준 값이 정답이다.