[백준 10844번] 쉬운 계단수 -python

문제 링크

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

10844번: 쉬운 계단 수

풀이 -다른 블로그 참고

동적 계획법 문제 

 

0을 제외한 모든 숫자는 맨 앞자리에 올 수 있다. 

dp[자리수][마지막 숫자] = 경우의 수 라고 할때 ,

 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

그러나, 마지막 숫자가 0일 때는 앞에 1만 올 수 있으므로 

dp[i][0] = dp[i-1][1]

 

마찬가지로 마지막 숫자가 9일 때는 앞에 8만 올 수 있으므로

dp[i][9] = dp[i-1][8]

n = int(input())

# dp[자리수][마지막 숫자] = 경우의 수 

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):
    dp[i][0] = dp[i-1][1] 
    dp[i][9] = dp[i-1][8]

for j in range(1,9):
  	dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

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