BOJ #10844 - 쉬운 계단 수

https://icpc.me/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)