[BOJ/C++] 11057 오르막 수

문제

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

풀이

10844랑 엄청 비슷한 문제
다만, 문제에서 수는 0으로 시작할 수 있다고 했으니까 DP를 0부터 초기화해줘야한다.

점화식 만드는 게 여전히 어렵다💦
항상 N과 N-1 관계 생각하기

DP[4][2] -> 2로 끝나는 4자리 숫자의 경우의 수 -> _ _ _ 2
DP[4][2] = DP[3][0] + DP[3][1] + DP[3][2] -> (? ? 0 + ? ? 1 + ? ? 2)

코드

#include <iostream>

using namespace std;

int dp[1001][10];

int main() {
	int N;
	int ans = 0;

	cin >> N;
	for (int i = 0; i < 10; i++) {
		dp[1][i] = 1;
	}

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

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

	return 0;
}