[백준] 10844번 - 쉬운계단수 (파이썬)

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

[코드]

N = int(input())

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

 

[아이디어

2자리의 1로 시작하는 쉬운계단수를 생각해보자 

두 가지가 가능하다 10, 12

n자리의 1로 시작하는 쉬운계단수를 생각해보자

(n자리 1로 시작하는 쉬운계단수 총개수) = (n-1자리 0으로 시작하는 쉬운계단수 총개수) + (n-1자리 2로 시작하는 쉬운계단수 총개수) 

그림으로 보면 다음과 같다