백준 11057 : 오르막 수 (Python)

출처 : https://www.acmicpc.net/problem/11057

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

for i in range(2, n + 1) :
    for j in range(10) :
        dp[i][j] = sum(dp[i - 1][:j + 1])

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

n자리의 오르막 수를 가정하면,

마지막 자리수가 0인 오르막 수는 마지막 자리수가 0인 n-1 자리의 오르막 수의 개수와 같다.

마지막 자리수가 1인 오르막 수는 마지막 자리수가 0, 1인 n-1 자리의 오르막 수의 개수의 합과 같다.

반복하면,

마지막 자리수가 9인 오르막 수는 마지막 자리수가 0~9인인 n-1 자리의 오르막 수의 개수의 합과 같다.

 

dp[i][j]는 마지막 자리수가 j인 i 자리의 오르막 수의 개수이며, 이는 마지막 자리수가 0~j인 i-1 자리의 오르막수의 개수의 합과 같다.