문제

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

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

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

입력

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

출력

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

다이나믹 프로그래밍 알고리즘을 적용하기 위해서는 아래와 같은 조건을 만족해야 한다.

• Overlapping Subproblem
• Optimal Substructure

Overlapping Subproblem 은 중복되는 부분 문제이다. 예를 들면 N번째 피보나치수를 구하는 문제를 구하는 문제는 N-1번째 N-2번째 피보나치 수를 구하는 문제가 되고 다른 수를 구할 때 같은 문제가 겹치는 경우가 생긴다.
큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야한다. 그리고 문제를 작은 문제로 나누어서 풀 수 있어야한다.

Optimal Substructure 문제의 정답을 작은 문제의 정답을 구할 수 있다. 다이나믹 프로그래밍에서는 작은 문제들을 한 번만 풀어야한다.(시간을 줄이려면 당연히) 그리고 정답을 구했으면 이 답을 어딘가 메모해놓고 (Memoization) 이 답들을 이용해서 큰 문제를 푼다. 그리고 저장되는 공간을 cache라고 한다. 따라서 DP를 구현하기 위해서는 메모를 작성하는 부분과 메모를 읽는 부분이 필요하다. (위 풀이에서는 이 메모가 배열에서 이루어진 것인가?)

다이나믹 프로그래밍 문제를 푸는 방법에는 크게 두가지가 있다.

• Top-down
• Bottom-Up

Top down 방식으로 문제를 푸는 방법은 다음과 같다.

1. 문제를 작은 문제로 나눈다.
2. 작은 문제들을 푼다.
3. 작은 문제들의 답으로 전체 문제를 푼다.

위의 피보나치 수열을 구하는 방법이 Top-down의 좋은 예이다. 주로 재귀함수를 이용해서 구현한다고 한다.

Bottom-Up 방식으로 문제를 푸는 방법은 다음과 같다.

1. 가장 작은 문제부터 푼다.
2. 문제의 크기를 점점 크게 만들어서 전체문제를 푼다.