[백준] 11057 오르막 수 파이썬

문제링크 : www.acmicpc.net/problem/11057

11057번: 오르막 수

문제 설명

 

푸는 방법

자세히 보면 수는 0으로 시작할 수 있다는 말이 있는데, 이는 01 02 03 04 05 도 가능하다는 말이 됩니다.

 

엥?? 그럼 1로 시작하는 건 당연히, 12 ~ 19까지, 2로 시작하는건 22~ 29 까지 8로 시작하는건 89까지 입니다.

 

그럼 [i][n]에 해당하는 값은 i-1에서 n~9까지의 값을 더하면 됩니다.

 

이전에 계단수 문제를 풀어봐서 다행히 생각보다 쉽게 풀 수 있는 문제였습니다. (www.acmicpc.net/problem/10844)

	n	0	1	2	3	4	5	6	7	8	9
dp	1	1	1	1	1	1	1	1	1	1	1
	2	10	9	8	7	6	5	4	3	2	1

 

코드

n = int(input())
dp = [0 for i in range(n+1)]
dp[1] = [1 for i in range(10)]

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

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