알고리즘 :: 백준 :: DP :: 11057:: 오르막 수

문제

문제 링크
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

문제접근

• N개의 공간이 있고, 임의의 idx번째 공간에 숫자 k를 넣으면, idx + 1번째 공간에는 k부터 넣을 수 있다.
• 임의의 idx번째 공간에 숫자 k를 넣기 위해서는 idx - 1번째 공간에는 1~k 숫자를 넣을 수 있다.
• 따라서 점화식을 세워보면, $D(n)(k) = \sum _1 ^kD(n-1)(i)$다.

코드

#include <cstdio>
#define MOD 10007

int N, dp[1001][10];
int solve(int n, int num) {
	if (n <= 0) return 0;
	if (dp[n][num] > 0) return dp[n][num];
	
	for (int i = num; i < 10; ++i) dp[n][num] = (dp[n][num] + solve(n - 1, i)) % MOD;
	return dp[n][num];
}
int main() {
	scanf("%d", &N);
	for (int i = 0; i < 10; ++i) dp[1][i] = 1;
	int answer = 0;
	for (int i = 0; i < 10; ++i) answer = (answer + solve(N, i)) % MOD;
	printf("%d\n", answer);
}

또는, forwarding으로 풀면,

#include <iostream>
#define MOD 10007
using namespace std;

int N, dp[1001][10];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < 10; ++i) dp[1][i] = 1;
	int n = 1;
	while (++n <= N) {
		for (int i = 0; i < 10; ++i)
			for (int j = i; j < 10; ++j) 
				dp[n][i] = (dp[n][i] + dp[n - 1][j]) % MOD;
	}
	int ans = 0;
	for (int i = 0; i < 10; ++i) ans = (ans + dp[N][i]) % MOD;
	cout << ans << '\n';
}

결과