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

문제

나의 답안

n=int(input())

dp = [[0] * 10 for _ in range(n + 1)]

for k in range(1,10):
    dp[1][k]=1#0으로 시작하는 수는 계단수가 아니므로 1로 초기화

for i in range(2,n+1):
    for j in range(10):
        if j==0:
            dp[i][j]=dp[i-1][j+1]#0일 때는 +1만 가능
        elif j==9:
            dp[i][j]=dp[i-1][j-1]#9일 때는 -1만 가능
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]#그외에는 +1,-1모두 가능
print(sum(dp[n])%1000000000)

접근 방법

• dp문제이므로 점화식을 도출해내면 된다.
  n=1일 때 9개, 1,2,3,⋯,9
  n=2일 때 17개, 10,21,23,32,34,43,45,⋯,87,89,98
• n=자리 수이고, 1의 자리에 오는 숫자(이하 j)가 무엇인지에 따라 앞에 올 수 있는 숫자가 달라진다.
  j=0일 때는 +1한 숫자만 올 수 있다. 즉, dp[n][j]=dp[n-1][j-1]
  j=1~8일 때는 +1,-1모두 올 수 있으므로 dp[n][j]=dp[n-1][j-1]+dp[n-1][j+1]
  j=9일 때는 -1한 숫자만 올 수 있다. 즉, dp[n][j]=dp[n-1][j+1]