[백준][11057번] 오르막 수

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

11057번: 오르막 수

 

풀이과정

 

1. dp문제이다.

 

2. N자리 수의 값이 K이면, N - 1 에 올 수 있는 값은 0 ~ K까지 이다.

 

dp[N][K] = dp[N - 1][0] + ... + dp[N -1][K]식을 구 할 수 있다.

 

소스코드

#include<stdio.h>

typedef unsigned long long ull;
ull dp[1001][10];
ull mod = 10007;
ull solution(int n)
{
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			dp[i][j] = 0;
			for (int k = j; k >= 0; k--) {
				dp[i][j] += dp[i - 1][k];
				dp[i][j] %= mod;
			}
			
		}
	}

	ull sum = 0;
	for (int i = 0; i <= 9; i++) {
		sum += dp[n][i];
	}
	return sum % mod;
}

int main()
{
	int n;
	for (int i = 0; i <= 9; i++) {
		dp[1][i] = 1;
	}
	scanf("%d", &n);
	printf("%llu\n", solution(n));
}