문제
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
입력
첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.
출력
첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.
아래 표는 문제 해결 과정에서 발견할 수 있는 규칙(?)이다.
표에 끝 자리수는 0, 1, 2, 3, 00, 01, 02, 03, 001, 002, 003등 숫자 자릿수 상관없이 끝에 나타나는 숫자들이다.
1자릿수 0~9까지 모두 0, 1, 2, 3, 4, ....,9한 개씩 존재하기 때문에 모든 표를 1로 채웠다.
2자릿수 ex) 00, 01, 11, 02, 12, 22 등 끝에 자릿수에 오는 숫자마다 올 수 있는 경우의 수들을 의미한다.
만약 3자릿수이고 끝에 수가 7로 끝난다면 어떤 경우의 수로 보면 될까?
??7인 경우라면 번호가 인접한 수인 7까지 허용되므로 7이하인 2자릿수의 경우의 수를 모두 더한 36이 된다.
그리고 아래 표를 보면 인접한 왼쪽에 위치한 값과 위쪽 값을 더해주면 1, 2, 3 등으로 끝나는 자릿수의 경우의 수가 나오는데 이것을 코드로 돌려가면서 대입해 주었다.
마지막에는 N 자리의 오르막 수의 모든 수를 구해야 하므로 해당행에 합들을 모두 더해 나타내주었다.
(DP는 많이 풀어봐야겠다는 생각뿐이다...)
