[BOJ] 11057. 오르막수

문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

---

풀이

1. DP[i][j] = i자리의 수 에서 j가 마지막 수로 왔을 경우, 오르막수의 개수

2. DP[1][j] = 1자리의 수는 j =0~9 까지는 전부 1 (문제에서 숫자가 0으로 시작할 수 있다 함)

3. Ex) DP[3][4] = 3자리의 수에서 마지막수가 4: A B 4

B, A = (0), (0) 

B, A = (1), (0, 1)

B, A = (2), (0, 1, 2)

B, A = (3), (0, 1, 2, 3)

B, A = (4), (0, 1, 2, 3, 4) 

3중 for문을 사용해서 DP[i][j] = DP[i][j] + DP[i-1][k];

---

코드

#include<iostream>

using namespace std;
const int MOD = 10007;
int DP[1001][10];

int main() {

	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][j] + DP[i - 1][k])%MOD;
		}
	}
	int result = 0;

	for (int i = 0; i < 10; i++) result = (result + DP[N][i]) % MOD;
	cout << result;
	return 0;
}