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

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

	1	2	3
1	1	2	3
2	1	3	6
3	1	4	10
4	1	5	15
5	1	6	21
6	1	7	28
7	1	8	36
8	1	9	45
9	1	10	55

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)