(c++)백준 11057번: 오르막 수

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

뒤에 오는 숫자를 신경써야 한다.

9 다음의 수는 9밖에 올 수 없다.

 

※점화식※

dp[i][j] : i번째 자리에 j가 올 때 경우의 수

※i=N부터, j=9부터 점화식 따라가기

 

if(j==9) dp[i][j] = dp[i+1][j] (j가 9이면 다음 숫자는 9밖에 못 온다.)

else dp[i][j] = dp[i][j+1] + dp[i+1][j] (9가 아니면 j보다 1 큰 수일 때 경우의 수에 다음 수가 j일 경우의 수 더하기)

 

#include <iostream>
using namespace std;

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

void DP() {
	for (int i = 0; i <= 9; i++) {
		dp[N][i] = 1;
	}
	for (int i = N - 1; i >= 1; i--) {
		for (int j = 9; j >= 0; j--) {
			//j가 9면 그 뒷자리 수는 9밖에 못옴
			if (j == 9)
				dp[i][j] = dp[i + 1][j] % 10007;
			//9이하는 뒷자리 수로 j와 j보다 큰 수가 올 수 있음
			else {
				dp[i][j] = (dp[i][j + 1] + dp[i + 1][j]) % 10007;
			}
		}
	}
	long long res = 0;
	for (int i = 0; i <= 9; i++) {
		res += dp[1][i];
	}
	cout << res % 10007 << endl;
}

int main() {
	cin >> N;
	DP();
	return 0;
}