백준 11057 오르막 수

 

 

만약 앞자리가 0이면 뒤엔 10개의 숫자가 올 수 있고, 1이면  9개~ 규칙이 이미 정해져있다.
그러므로  dp[i][j] += dp[i - 1][k]; 라는 점화식을 도출 해낼 수 있다.

#include <iostream>
using namespace std;
#define mod 10007

int main()
{
	int n;
	int dp[1001][10] = { 0 };
	int sum = 0;

	cin >> n ;

	for (int m = 0; m < 10; m++)
	{
		dp[1][m] = 1;
	}
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int k = j; k <= 9; k++)
			{
				dp[i][j] += dp[i - 1][k];
				dp[i][j] = dp[i][j] % mod;
			}
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		sum += dp[n][i];
	}
	cout << sum % mod << "\n";
	return (0);
}

//모듈러를 사용하는 이유는 오버플로우를 막기위해서이다!