백준 알고리즘, 11057 문제

---

풀이

오르막 수 문제는 이전 계단 문제와 마찬가지로 2차원 배열을 활용해서 풀어낼 수 있다.

문제를 읽어보면 각 자리수에 어떤 수 j 가 온다면 그 수의 다음에 올 수 있는 수는 j ~ 9 까지가 된다는 것을 알 수 있다.

점화식은 다음과 같다.

DP[N][j] = sum ( DP[N - 1][j ...9] );

즉, 어떤 값 N 의 특정 자리수 j 의 값은 N - 1 의 자리수의 j 값 부터 9 까지의 모든 해를 더한 것과 같다.

ps..

위 표를 보면 위 값을 전부 더하는 방식(알고리즘에 따른 방식)은 3 중 for 문을 구성해야한다.

그러나 자리값의 해가 DP[N][J] = DP[N][j - 1] - DP[N - 1][j - 1] 로도 구해진다.

따라서 2 중 for 문으로도 표현할 수 있다.

---

코드

@github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/11057
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 23
 */
#include <iostream>
using namespace std;
int main() {
    int DP[1001][10] = { 0, };
    int i, j, k, N, sum = 0, ans = 0;
    cin >> N;
    for (i = 0; i < 10; i++) DP[1][i] = 1;
    for (i = 2; i <= N; i++) {
        for (j = 0; j < 10; j++) {
            sum = 0;
            for (k = j; k < 10; k++) {
                sum = sum % 10007 + DP[i - 1][k] % 10007;
            }
            DP[i][j] = sum % 10007;
        }
    }
    for (i = 0; i < 10; i++) ans = ans % 10007 + DP[N][i] % 10007;
    cout << ans % 10007 << endl;
    return 0;
}