[BOJ/백준] 10844 - 쉬운 계단 수 (Python)

문제

문제링크

각 계단은 모든 자리 차이가 1이고 0으로 시작하는 수는 없다.

길이 n인 계단 수가 총 몇 개 있는가?

 

풀이

n=1일 때, 0으로 시작하는 경우는 없으므로 dp[1][0]은 0이다. 나머지는 모두 1이다.

n이 2 이상일 때, 이번 자리수가 0이면 이전 자릿수는 무조건 1에서 와야하므로 dp[i-1][1]과 같다.

이번 자리수가 0인 경우도 이전 자릿수는 무조건 8에서 와야하므로 dp[i-1][8]와 같다.

나머지 경우에는 현재 자리수보다 1 작거나 큰 수에서 올 수 있으므로 dp[i-1][j-1]+dp[i-1][j+1]가 된다.

 

코드

import sys
input=sys.stdin.readline

n=int(input().strip())
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][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])%1000000000)