[알고리즘][백준] 10844번 쉬운 계단 수 - 파이썬(python) 풀이

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

10844번: 쉬운 계단 수

---

나의 아이디어는 끝나는 숫자별로 뒤에 올 수 있는 숫자가 한정되어 있어

1 -> 0
2 -> 1, 3
3 -> 2, 4
...
8 -> 7, 9
9 -> 8

 

각 숫자로 끝나는 수의 개수로 2차원을 만들어 dp 진행해보았다!!

import sys

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

# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 로 끝나는 수의 개수
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
dp[2] = [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]

for i in range(3, n+1):
    for j in range(11):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 1:
            dp[i][j] = dp[i-1][0] + dp[i-1][2]
        elif j == 2:
            dp[i][j] = dp[i-1][1] + dp[i-1][3]
        elif j == 3:
            dp[i][j] = dp[i-1][2] + dp[i-1][4]
        elif j == 4:
            dp[i][j] = dp[i-1][3] + dp[i-1][5]
        elif j == 5:
            dp[i][j] = dp[i-1][4] + dp[i-1][6]
        elif j == 6:
            dp[i][j] = dp[i-1][5] + dp[i-1][7]
        elif j == 7:
            dp[i][j] = dp[i-1][6] + dp[i-1][8]
        elif j == 8:
            dp[i][j] = dp[i-1][7] + dp[i-1][9]
        elif j == 9:
            dp[i][j] = dp[i-1][8]

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

10844_쉬운계단수.py

0.00MB