05.11. 오르막 수 [Dynamic Programming][백준 11057]

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

11057번: 오르막 수

 

Algorithm classification : Dynamic Programming

 

05.11.1. Problem

An ascending number is a number whose digits are in ascending order. At this time, even if the adjacent numbers are the same, they are played in ascending order.

For example, 2234, 3678, and 11119 are uphill numbers, but 2232, 3676, and 91111 are not uphill numbers.

Write a program to find the number of ascending numbers given a number length N. Numbers can start with 0.

 

05.11.2. Input limit

The first line gives N (1 ≤ N ≤ 1,000).

 

05.11.3. Output

The first line prints the remainder of dividing the number of ascents of length N by 10,007.

 

05.11.4. Solution

쉬운 계단 수와 유사한 문제입니다. dp table인 array a[i][j]를 길이가 i이고 첫 자릿수가 j인 오르막 수의 갯수라고 정의한다면 최종적으로 

를 출력하면 됩니다. 

int main()
{
	int n;
	scanf("%d", &n);
	int a[n+1][10] = {0};
	int sum = 0, i, j, k;
	
	for(i = 0; i < 10; i++)	a[1][i] = 1;
	
	for(i = 2; i <= n; i++){
		for(j = 0; j < 10; j++){
			for(k = 0; k <= j; k++)
				a[i][j] = (a[i][j] + a[i-1][k]) % 10007;
		}
	}
	for(i = 0; i < 10; i++)
		sum = (sum + a[n][i]) % 10007;
	
	printf("%d", n == 1 ? 10 : sum);
	
	return 0; 
}