10844번 - 쉬운 계단 수

문제

10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

풀이

dp[i][j] 에 대해서, 길이가 i 일 때 맨 뒤 숫자가 j 일 경우 가능한 계단 수를 목표로 점화식을 작성한다.

N = int(input())

dp = [[0]*101 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]) % (10**9)

print(sum(dp[N]) % (10**9))