[알고리즘/백준] 11057: 오르막 수(python)

마지막에 끝나는 수로 생각해서 풀었다.

1. 0으로 끝나려면 이전의 수가 0
2. 1로 끝나려면 이전 수가 1 이하
3. 2로 끝나려면 이전 수가 2 이하
   ...
4. 9로 끝나려면 이전 수가 8 이하...
   경우의 수를 다 더해주면 답이 나온다.

ex) dp[i][9] = dp[i-1][8] + dp[i-1][7] + dp[i-1][6] + dp[i-1][5] + dp[i-1][4] + dp[i-1][3] + dp[i-1][2] + dp[i-1][1] + dp[i-1][0]

N = int(input())
dp = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for _ in range(N+1)]
dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, N + 1):
    dp[i][0] = 1
    s = 1
    for j in range(1, 10):
        s += dp[i-1][j]
        dp[i][j] = s % 10007
print(sum(dp[N]) % 10007)