📌 [BOJ] 10844 쉬운 계단 수

📖 문제

📖 예제

📖 풀이

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
  dp[1][i] = 1

for i in range(1,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]

print(sum(dp[-1])%1000000000)

사람들의 풀이를 통해 겨우 문제를 이해한 문제이다.
점화식을 외움으로써 풀 수 있어진 것 같다.
어려운 문제다. . .