오르막 수 (feat. 백준, 11057번)

오르막 수
https://www.acmicpc.net/problem/11057

11057번: 오르막 수

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11057
#include <iostream>
#include <numeric>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, dp[1001][11] = { 0 };
	for (register int i = 0; i < 10; ++i)
		dp[1][i] = 1;
	cin >> N;
	for (register int i = 2, j; i <= N; ++i)
		for (j = 0; j <= 9; ++j)
			dp[i][j] = accumulate(&dp[i - 1][j], &dp[i - 1][10], 0) % 10007;
	cout << accumulate(&dp[N][0], &dp[N][10], 0) % 10007 << endl;
	return 0;
}
// *&)*@*

1. N=1일때는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 로 10개입니다.
2. N=2일때는 0 뒤에는 0~9, 1 뒤에는 1~9, 2 뒤에는 2~9, ..., 9 뒤에는 9 가 올수 있습니다.
3. 따라서 오르막 수 N개에 대한 각 자리수별 개수는 Pn,x 라고 하면
   Pn,0 = Pn-1,0 + Pn-1,1 + ... + Pn-1,9
   Pn,1 = Pn-1,1 + Pn-1,2 + ... + Pn-1,9
   ...
   Pn,9 = Pn-1,9 라는 수식이 성립됩니다. (단, n >= 2인 경우)