[Python] 쉬운 계단 수 - 백준 (DP)

해당 글은 백준 10844번 '쉬운 계단 수' 문제를 다룬다.

문제

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

10844번: 쉬운 계단 수

 

설명

해당 문제는 1자리 수 일 때, 계단자리수는 0~9까지 수에서 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]로 카운트할 수 있다.

2자리 수 이상 일 때 부터 0일 때는 0이 앞에 올 수 없으므로 이전의 1의 갯수를,

9일 때는 올 수 있는 수는 8 밖에 없으므로 이전의 8의 갯수를 가져온다.

1~8일 때는 앞뒤로 두 개의 숫자가 올 수 있으므로 이전의 앞뒤 숫자의 갯수를 가져온다.

표로 그려보자면 자릿수에 따른 0~9의 DP는 아래와 같이 구현된다.

	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

 

코드

n = int(input())

dp = [[0]*10 for _ in range(n+1)]
for i in range(1, 10):
    dp[1][i] = 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)