11057)오르막 수

문제 요약

오르막 수는 오른 쪽에 있는 수가 왼쪽에 있는 수보다 같거나 큰 수를 말한다. (*0으로 시작 할 수도 있다.)
자릿수 n이 주어졌을 때, 가능한 오르막 수의 갯수를 구하는 문제

풀이

다른 dp문제처럼 n-1자릿수의 값을 이용해 n자릿수의 경우의 수를 구한다. 예를 들어 자연수 i가 마지막 n자릿수에 오는 경우의 수는 n-1에 0이 오는 경우의 수부터 i가 오는 경우의 수까지 모두 더한 값이다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int num;
    cin>>num;   
    vector<vector<int>> num_arr;
    for(int i=0;i<10;i++){
        vector<int> *tmp = new vector<int>;
        tmp->push_back(1);
        num_arr.push_back(*tmp);
        delete tmp;
    }
    for(int i=1;i<num;i++){
        //i+1자릿수의 각 숫자의 갯수 구하기
        for(int j=0;j<10;j++){
            int sum=0;
            for(int k=0;k<=j;k++)
                sum= (sum +num_arr[k][i-1])%10007; 
            num_arr[j].push_back(sum);
        }
    }

    int sum=0;
    for(int i=0;i<10;i++)
        sum=(sum+num_arr[i][num-1])%10007;
    cout<<sum<<endl;
}