[백준] 11057: 오르막 수 (Python)

문제📖

풀이🙏

• data[i][j]에서 i는 자리수, j는 끝에 오는 숫자라고 한다.
• data[i][j]에서 앞에 올 수 있는 수는 j보다 작거나 같은 수가 와야하므로 다음과 같이 점화식을 만들 수 있다.
  dp[i][j] += dp[i-1][k] (k는 j보다 작거나 같은 수)

코드💻

n = int(input())
dp = [[0] * (10) for i 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)