[백준][Python][11057][DP] 오르막 수

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

11057번: 오르막 수

이 문제는 고생 많이한 문제다.

 

문제의 해결법은 다음과 같다.

d[i] 를 i+1 번째 자릿수의 앞자리 로 하자.

1자리 숫자들은 전부 오르막 수로 볼수 있기 때문에 1로 초기화한다.

이제 생각해보면

12,13,14.. 23,24,25..등등은 전부 오르막 수인데,

1 + (1이상 수 ) , 2+ (2이상 수) 라고 보면 n이상의 수를 전부 더하는것과 마찬가지다.

이 개념을 생각하고 보면 된다 ( j index가 바로 이부분이다.)

i 인덱스는 0-9까지 각 자리수를 연산하는 반복문 자리고, a는 n까지 계산하는데 쓴다.

 

n = int(input())

modv = 10007
d = [[1,1,1,1,1,1,1,1,1,1]]

for a in range(1,n):
    tmp = [0]*10
    for i in range(10):
        for j in range(i,10):
            tmp[i] += d[a-1][j]
            tmp[i] %= 10007

    d.append(tmp)


print(sum(d[-1])% 10007)