[파이썬] 백준 10844 쉬운 계단 수

< 처음 풀이 >

문제 이해를 하지 못했고, 동적 풀이법 역시 몰랐다.

 

< 해결 방법 >

문제 이해는 하였고, 푸는 방법도 대략적으로는 알았지만 잘 풀리지 않아 구글링을 통해 해결을 하였고 코드가 이해는 되었다.

 

N = int(input())
 
dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1
 
MOD = 1000000000
 
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]) % MOD)