[algorithm] 백준 - 오르막수

 

DP 문제이다.

문제의 포인트는 0부터 시작할 수 있다는 것과 오름차순 수열, 그리고 인접한 수가 같아도 된다는 것이다.

자릿수가 1일 때,

0 1개
1 1개
2 1개
...
9 1개

로 10개이고,

 

자릿수가 2일 때,

수열의 마지막 수	다음에 올 수 있는 수
0	0,1,2,3...9
1	1,2,3,4...9
2	2,3,4,5...9
...	...
9	9

총 55개 라는 것이다.

그럼 수열의 마지막 수를 j라 하고 올 수 있는 수를 k라 했을 때,

j에서 k만큼의 경우의 수를 더한다는 것을 알 수 있다.

 

코드로 표현해보면 이렇다.

// 오르막수
#include <iostream>
using namespace std;

int main(void){
    int count, total = 0,dp[1001][10] = {0};
    cin >> count;
    for(int i = 0; i < 10; i++){
        dp[1][i] = 1;
    }
    for(int i = 2; i <= count; i++){
        for(int j = 0; j < 10; j++){
            for(int k = j; k < 10; k++){
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % 10007;
            }
        }
    }
    for(int i = 0; i < 10; i++){
        total = (total + dp[count][i]) % 10007;
    }
    cout << total;
}