11057(dp)

첫인상

dp 문제다

풀이

dp의 변수로 0~9까지의 수 n과 n을 가장 뒷 자리로 하는 수의 길이 m으로 뒀을 때 dp[n][m]을 가짓수로 두고 dp를 짜주었다

코드

#include<iostream>
using namespace std;

int dp[10][1005];

int main() {
	int n;

	cin >> n;

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

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

	int ans = 0;
	for (int i = 0; i < 10; i++) {
		ans += dp[i][n - 1];
	}

	cout << ans % 10007;
}