[BOJ]11057. 오르막 수

문제:

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

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

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

입력:

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

출력:

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

풀이 방법:

2차원 동적배열을 사용해서 풀었다. 가로축을 0~9까지의 수, 세로축을 1~N까지의 길이의 수라고 설정했다. 초기에는 길이가 1인 오르막 수은 각 수 별로 1씩 있다는 것을 쉽게 알 수 있다. ( why? 0 , 1, 2, 3, 4, 5, .. , 9 = > 10개)

3까지 직접 숫자를 쓰다보면 길이가 1씩 증가할 때마다 일정한 규칙에 의해서 값이 증가한다는 것을 알 수 있다.

예를 들면 길이가 2이고 처음 0으로 시작하는 오르막 수는 동적배열에서 길이가 1인 행에서 0~9까지의 합이다.

그리고 길이가 2이고 처음 1으로 시작하는 오르막 수는 동적배열에서 길이가 1인 행에서 1~9까지의 합이다.

즉 길이가 n이고 처음 M으로 시작하는 오르막 수는 2차원 동적배열에서 길이가 n-1인 행에서 M~9까지의 합이라는 것이다. 이 규칙에 의해서 n까지 2차원 배열을 확장한 후 n번째에 있는 행의 합을 구하면 길이가 N인 오르막 수의 개수임을 알 수 있다.

n=int(input())
answer=[[1]*10]
dp=[1]*10
for i in range(1,n):
    answer.append(dp)
    for j in range(10):
        answer[i][j]=sum(answer[i-1][j:])
print(sum(answer[n-1])%10007)