BOJ #10844 - 쉬운 계단 수

https://www.acmicpc.net/problem/10844

# 문제 분류

Dynamic Programming

풀이 접근 방법

1. 0으로 시작하는 수는 없다는 점을 생각하며 DP 테이블을 작성해보자.
2. 그러면 0 → 1 만 가능, 9 → 8 만 가능하다는 것이 보이게 된다.
3. dp[0] = prev[1], dp[9] = prev[8], dp[n] = prev[n-1] + prev[n+1] (n != 0, 9)로 점화식을 세울 수 있다.

밑 python 코드에서는 tmp 배열이 prev의 역할을 하며, 계속해서 갱신된 dp 배열을 tmp 배열로 deepcopy 해주는 방식.

소스 코드

import copy as cp

size = int(input())

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

for i in range(size-1):
    tmp = cp.deepcopy(cpy)
    tmp[0] = dp[1]
    tmp[9] = dp[8]
    for j in range(1, 9):
        tmp[j] = dp[j-1] + dp[j+1]
    dp = cp.deepcopy(tmp)

print(sum(dp) % 1000000000)