오르막 수

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

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

첫 번째 자리수 부터, 경우를 따지게 되는데, 뒷 자리로 갈수록 수는 커지거나 같아야한다.
여기서 알 수 있는 것은, 주어진 자리수의 맨 끝 자리수가 9일 경우, 그 앞에 오는 숫자들은, 모두 9보다 크거나 같아야하고, 이 경우의 수를 이용하면 풀 수 있는 문제이다.

n이 3이고, 끝 수가 2인 오르막 수의 개수는, n=2 일 때, 끝 수가 0일 때, 1일 때, 2일 때의 값을 모두 더한 값이 되게 되는데 이 연관성을 찾는 것이 문제 푸는데 가장 중점이라고 생각했다.
즉 asc[3][2] = asc[2][0] + asc[2][1] + asc[2][2] 를 만족하게 된다.

코드로 살펴보자

import sys

input = sys.stdin.readline

N = int(input())
asc = list([[1]*10])
for _ in range(N):
    asc.append(list([0]*10)) #N자리수 케이스 저장
for i in range(1,N+1):
    for j in range(0,10):
        for temp in range(j+1):
            asc[i][j] += asc[i-1][temp]
print(asc[N][9]% 10007)

DP 문제는 점화식을 찾고, 전후 관계의 연관성을 찾는 것이 가장 핵심이고, 이를 푸는데 머리를 많이 써야하는 것 같다.