[백준 문제풀기] #10844번 - 쉬운 계단 수 with Python

 

🙆🏻‍♀️ How to solve

다이나믹 프로그래밍 문제이다. 

 

길이가 1인 계단 수 = 1,2,3,4,5,6,7,8,9       9개 

길이가 2인 계단 수 = 10, 21,(12,32),(23,43),(34, 54), (45, 65), (56,76), (67,87), (78,98) , 89  17개 

길이가 3인 계단 수 = 210, (321, 121), (212,312,232,432), (123, 323, 343, 543) .... 

 

문제를 풀 때 일의 자리수에 올 수 있는 숫자는 0~9까지이다. 

• 가장 뒤에 오는 숫자 = 0
  • dp[자릿수][0] = dp[자릿수 - 1][1]
• 가장 뒤에 오는 숫자 = 1~8
  • dp[자릿수][가장 뒤에 오는 숫자] = dp[자릿수 - 1][가장 뒤에 오는 숫자 - 1] + dp[자릿수 - 1][가장 뒤에 오는 숫자 + 1]
• 가장 뒤에 오는 숫자 = 9
  • dp[자릿수][9] = dp[자릿수 - 1][8]

 

 

💻 Code

import sys

n = int(sys.stdin.readline())
dp = [[0] * 10 for _ in range(n+1)]

# 자릿수가 1인 경우 
for i in range(1, 10):
    dp[1][i] = 1

# 자릿수가 2이상인 경우 
for i in range(2, n+1):
    for j in range(10):
        # 맨뒤 자릿수 숫자가 0
        if (j == 0):
            dp[i][j] = dp[i-1][1]

        # 맨 뒤 숫자가 1~8
        elif (1 <= j <= 8):
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

        # 맨 뒤 숫자가 9
        else:
            dp[i][j] = dp[i-1][8]

print(sum(dp[n]) % 1000000000)