BOJ ::11057 오르막 수 (C++)

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

11057번: 오르막 수

DP문제

DP[N][L] : N 자리 수에 L 이 올 경우, 오르막 수 조건에 해당하는 경우의 수

ex) DP[3][5] -> _ _ 5 (3번째 자리의 5가 올경우)

 

점화식:
DP[N][L] = DP[N-1][0] + DP[N-1][1] + ... + DP[N-1][L-1] + DP[N-1][L]

한 자리인 경우는 무조건 1이므로 DP[1][i] = 1로 초기화 한다.

 

갯수를 10007로 나눈 나머지를 구해야하므로 꼭 mod 처리 해줘야 한다.

 

 

#include <iostream>
using namespace std;

int dp[1001][10];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	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;
			}
			
		}
	}
	int ans = 0;
	for (int j = 0; j < 10; j++)
		ans += dp[n][j];

	ans %= 10007;
	cout << ans << "\n";
	ret