[Python] 백준 11057 오르막 수

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

11057번: 오르막 수

 

문제 해결

n자리 수일 때 앞에서부터 n-1번째 수에 무슨 수가 오느냐에 따라 n자리에 올 수 있는 숫자의 개수가 달라짐

따라서 n번째 숫자에 i가 올 경우의 수를 dp[n][i]라 하면

$$dp[n][i] = \sum_{k=0}^i dp[n-1][k]$$

1자리 수일 때 i가 어느 수던간에 dp[n][i] = 1이므로

dp를 이용해서 쉽게 풀 수 있다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0 for _ in range(10)] for _ in range(n+1)]
for i in range(10):
    dp[1][i] = 1 # 한자리수는 0~9 각각 1개
for i in range(2,n+1):
    for j in range(10):
        dp[i][j] = (sum(dp[i-1][:j+1]))%10007
ans = (sum(dp[n][:]))%10007
print(ans)