[백준OJ] 11057번 오르막 수

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

11057번: 오르막 수

---

 

-풀이-

먼저 1자리수의 오르막수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 있다.

2자리수의 오르막수중 맨 앞자리가 0인수는 00, 01,02,03, ... , 09가되고,

2자리수의 오르막수중 맨 앞자리가 1인수는 11,12,13,14,15,16,17,18,19가된다.

3자리수의 오르막수중 맨 앞자리가 0인수는 000, 001, 002, .... , 011, 012, 013, 014, 015, .... , 099 가 된다.

 

규칙이 보이지 않는가?

N자리수의 오르막 수 중 맨 앞자리가 i인 수의 개수를 구하기 위해선, N-1자리수의 오르막수중 맨 앞자리가 i보다 크거나 같은수들의 개수를 모두 더한것과 같아진다.

 

따라서 DP[N][I] = K (N자리수의 오르막수중 맨 앞자리가 I인 수의 개수 = K ) 라고 한다면,

DP[N][I] = DP[N-1][I] + DP[N-1][I+1] + DP[N-1][I+2] + .... + DP[N-1][9] 가 된다.

이때 DP[1][0]~DP[1][9]는 모두 1로 초기화를 해주어야한다.

 

이렇게 DP[N][0]~DP[N][9]까지 모두 구한뒤, 더해주면 답이 나온다.

 

-시간복잡도-

O(N)이 된다.

 

-코드-

#include <iostream>
#include<algorithm>
using namespace std;

long long dp[1001][10] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	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 <= 9; j++) {
			for (int k = j; k <= 9; k++) {
				dp[i][j] += (dp[i - 1][k]);
			}
			dp[i][j] %= 10007;
		}
	}
	long long result = 0;
	for (int i = 0; i <= 9; i++) {
		result = (result+dp[n][i])%10007;
	}
	cout << result;
	return 0;
}