BOJ11057 오르막 수

1. 문제링크 : BOJ11057 : 오르막 수

2. 문제요약

 - 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. (인접한 수가 같아도 오름차순으로 친다)
 - 예를 들어, 2234, 3678은 오르막 수이지만, 2232, 91111은 오르막 수가 아니다.
 - 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 것이 목표이다.
 - 수는 0으로 시작할 수 있다.

3. 문제풀이

 - Dynamic Programming을 이용한다.
 - dp[i][j]를 <길이가 i이고 끝자리가 j인 오르막 수의 개수>로 정의한다.
 - 인접한 수가 같아도 오름차순이라고 생각하므로, dp[i][j]는 (길이가 1 작으면서 끝자리가 j인 오르막 수의 개수) + (길이는 같으면서 끝자리가 j - 1인 오르막 수의 개수)가 된다.
 - 즉, dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다.
 - 이 점화식을 반복문으로 구현해 goal인 sum(dp[n][i], 0 < i < 10)을 구한다.

4. 소스코드 ( C++ - 헤더파일을 제외하고 C와 같음 )