백준_11057_오르막수

다이나믹 프로그래밍(dp) 문제였다.

d[i][j]는 자릿수가 i일때 마지막이 j인 오르막수의 개수이다.

마지막이 j려면 그 전 숫자 (자릿수가 i-1인 숫자 = d[i-1][☆] ) 에서 ☆에 들어갈 숫자가 0, 1, 2, ··· j 여야 한다. (그래야 오르막수이다.)

따라서, 모든 경우를 3중 for문을 통해 계산할 수 있었다.

첫번째 for문은 자릿수를 증가시키고, 두번째 for문은 해당 자릿수인 숫자의 마지막 수가 무엇인지 따지고, 세번째 for문은 마지막 수를 고려해서, 그 전 숫자(자릿수가 하나 적은)의 값들을 더함으로써 실제로 오르막수의 개수를 구하기 위해 사용된다.

#include <iostream>
#define MAX 1001
#define MOD 10007

using namespace std;

int N, answer;
long long d[MAX][10];

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

	for (int i = 0; i < 10; i++)
		answer += d[N][i];
	answer = answer % MOD;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	dp();
	cout << answer << '\n';
	return 0;
}