11057_오르막수

문제: 

00, 01, 119 이렇게 각 자리가 뒤로 갈수록 커지는 수를 오르막수라고 한다. 입력값이 주어졌을 때 입력값의 길이 만큼의 오르막수가 몇개인지

구하라

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int main() {

	int dab = 0;
	int input;
	cin >> input;

	int **dp = new int*[input];//열을 먼저만들고
	for (int i = 0; i < input; i++) {//열만큼 반복하고
		dp[i] = new int[10];//열에 행하나씩 넣는다.
		memset(dp[i], 0, (sizeof(int)*10));//memset으로 0을 넣어준다.
	}//2차원배열 선언

	for (int r = 0; r < 10; r++) {
		dp[0][r] = 1;
		
	}//먼저 초항을 1로 지정한다 이 문제는 갯수를 세는 것이므로 1로 초기화 해주어 갯수를 세어줄 수 있다.

	for (int a = 1; a < input; a++) {
		for (int b = 0; b < 10; b++) {
			for (int c = b; c < 10; c++) {
				dp[a][b] = (dp[a][b] % 10007 + dp[a - 1][c] % 10007) % 10007;
			}
			//cout << "dp[" << a << "][" << b << "] = " << dp[a][b] << endl;// 결과값을 중간중간 볼 수 있는 명령문
		}
	}

	//0 1 2 3 4 5 6 7 8 9 --dp[0][0] ~ dp[0][9];

	//00 01 02 03 ... 09 --dp[1][0] = dp[0][0]+dp[0][1]+..dp[0][9];
	//   11 12 13 ... 19 --dp[1][1] = dp[0][1]+dp[0][2]+..dp[0][9];
	//......................................
	//	....			 --dp[1][9] = dp[0][9]


	
	for (int d = 0; d < 10; d++) {
		dab += dp[input - 1][d]%10007;
	}


	cout << dab%10007;
	return 0;
}