[Algo] 백준 10844_쉬운 계단 수

백준 10844_쉬운 계단 수

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

N = int(input())
dp = [[0]*12 for _  in range(N + 1)]
dp[1][2:11] = [1]*9

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

print(sum(dp[N]))

• N이 1일 때는 1,2,3,4,5,6,7,8,9 각 숫자들이 한번씩 사용된다.
• N이 2일 떄는 1에 의해 (0,1) 2에 의해 (1,3) 등등가가 숫자에서 -1,+1 한 숫자들이 생성이 된다.
• N이 1일 때의 숫자들에 의해 생성된 N이 2일 때의 숫자들
• So dp[i-1][j-1] + dp[i-1][j+1]로 계산한다.