[백준 BOJ][C++]11057번 오르막 수 풀이: DP

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

11057번: 오르막 수

 

이 문제는 Dynamic Programming, DP로 해결할 수 있습니다. 

 

dp[i][j] = 숫자 i로 시작하는 j 자리 오르막 수의 개수 (i: 0~9, j: 1~N)

 

초깃값은 dp[0][1] 부터 dp[9][1]은 전부 1이 되겠죠?

 

dp[0][2] 는 어떻게 될까요 가능한 수가 00, 01, 02, 03, 04, 05, 06, 07, 08, 09 총 10개입니다. 

dp[1][2] 는 11, 12, 13, 14, 15, 16, 17, 18, 19로 9개 입니다. 

 

dp[0][3]은 000, 001, 002, 003, 004, 005, 006, 007, 008, 009,

              011, 012, 013, 014, 015, 016, 017, 018, 019, ... 으로 쭉 나아가겠죠

 

규칙이 보이시나요?

 

dp[0][3]은 0으로 시작하는 3자리의 오르막 수의 개수는 dp[0][2]+dp[1][2]+...+dp[9][2]의 합과 같습니다. 

dp[1][3]은 dp[1][2]+dp[2][2]+...+dp[9][2]가 되겠죠?

 

점화식은 다음과 같습니다. 

 

dp[i][j]=dp[i][j-1]+...+dp[9][j-1]

 

#include<iostream>
#include<cstdlib>
#include<vector>

using namespace std;

#define mod 10007

long long dp[10][1001];

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	long long ans = 0;

	cin >> n;

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

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

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

	cout << ans % mod;

	return 0;
}