[백준/Python]11057_오르막 수

문제

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

11057번: 오르막 수

풀이

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

표에서 n은 자릿수, n 옆에 숫자들은 n 자리 수의 맨 마지막 숫자, sum은 행의 합을 의미합니다.

다이나믹 프로그래밍으로 풀면 점화식을 구할 수 있는데 'dp[i][j] = dp[i-1][0]부터 dp[i-1][j]까지 합'으로 표현할 수 있습니다.

코드

import sys

n = int(sys.stdin.readline().rstrip())
dp = [[0] * 10 for _ in range(n + 1)]
for i in range(10):
    dp[1][i] = 1
for i in range(2, n + 1):
    for j in range(10):
        for k in range(j + 1):
            dp[i][j] += dp[i - 1][k]
print(sum(dp[n]) % 10007)