[BAEKJOON] 오르막 수 - python

오르막 수

알고리즘 - dynamic programming

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

 

solution 1

n = int(input())
dp = [1]*10

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

print(sum(dp)%10007)

 

solution 2

N = int(input())
arr = [[0] * 10 for i in range(1001)] #1자리~1000자리
for i in range(10):
    arr[1][i] = 1
for i in range(2, 1001): #길이 i
    for j in range(10): #마지막숫자 j
        for k in range(j + 1):
            arr[i][j] += arr[i - 1][k]
print(sum(arr[N]) % 10007)