[백준] 11057-오르막 수 [Python(파이썬)]

문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

풀이

쉬운 계단 수 문제와 아주 유사한 문제다. 하지만 수가 0으로 시작될 수 있다는 점에서 주의해야 한다.

• 맨 앞자리 수가 0이면 다음 숫자로 0~9까지 다 올 수 있으므로 dp[i][0] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][8] + dp[i-1][9]
• 맨 앞자리 수가 1이면  다음 숫자로 1~9까지 올 수 있으므로 dp[i][1] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][8] + dp[i-1][9]

따라서 dp[i][j] += dp[i-1][k] (k -> j to 10)가 성립한다. 

 

출력할 때 mod연산해주는 것에 주의한다.

 

코드

n = int(input())
MOD = 10007
dp = [[0 for _ in range(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, 10):
            dp[i][j] += dp[i-1][k]

print(sum(dp[n]) % MOD)