백준 11057번(오르막 수)

백준 10844(쉬운 계단 수) 와 비슷한 문제이다.

 

핵심로직

 

1. 2차원 배열로 작은 조각에서 각각 접근해야 한다.

 

2. 점화식은 아래와 같다.

#include <iostream>

using namespace std;

int N;
long long dp[10][1001];
long long result;

int main(void) {
	cin >> N;

	for (int i = 0; i < 10; i++)
	{
		dp[i][1] = 1;	// 초기값 셋팅
	}

	for (int x = 2; x <= N; x++)
	{
		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j <= i; j++)
			{
				dp[i][x] = (dp[i][x] + dp[j][x - 1])%10007;
			}
		}
	}

	for (int i = 0; i < 10; i++)
	{
		result = (result + dp[i][N])%10007;
	}

	cout << result;

	return 0;
}