DP) 11057.오르막 수

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

11057번: 오르막 수

규칙

1. 수의 자리가 오름차순을 이루는 수
2. 인접한 수가 같아도 오름차순으로 친다.
3. 수는 0으로 시작할 수 있다.

목표

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

Solution

1. d[i][j] = 길이가 i이고 마지막 수가 j인 오르막수의 개수
2. 점화식 : d[i][j] = ∑d[i-1][k] ( 0 <= k <= j )
3. d[1][i]=1

소스 코드

n=int(input())

d=[[0]*10 for _ in range(n+1)]

mod=10007

for i in range(1,n+1):
    for j in range(10):
        if i==1:
            d[i][j]=1
        else:
            for k in range(j+1):
                d[i][j] += d[i-1][k]
        d[i][j]%=mod

ans=0
for j in range(10):
    ans+=d[n][j]

print(ans%mod)