BOJ 10844 쉬운 계단 수

문제

접근 방법

모든 경우의 수를 구하기는 어렵다.

dp를 통해 구해보고자 하였다. 10xn 배열을 만들어서 dp[i][j] $\rightarrow$ j 자릿수에서 끝자리가 i인 계단 수를 저장하여 메모이제이션을 한다.

점화식은 계단 수를 만족하기 위해 dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1]을 사용한다.

정답 코드

import sys
input = sys.stdin.readline

n = int(input())

if n==1:
  print(9)

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

  # 각 자릿수별로 계산
  for j in range(1,n):
    for i in range(10):
      if 0<=i-1 and i+1<=9:
        dp[i][j] = (dp[i-1][j-1] + dp[i+1][j-1])%1000000000
      elif 0<=i-1:
        dp[i][j] = dp[i-1][j-1]%1000000000
      else:
        dp[i][j] = dp[i+1][j-1]%1000000000

  result = 0

  for i in range(10):
    result += (dp[i][n-1])%1000000000
  print(result%1000000000)