05.10. 쉬운 계단 수 [Dynamic Programming][백준 10844]

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

10844번: 쉬운 계단 수

 

Algorithm classification : Dynamic Programming

 

05.10.1. Problem

Let's look at the number 45656.

The difference between all adjacent digits of this number is 1. This number is called the number of steps.

Given N, find the total number of steps of length N. Numbers starting with 0 are not steps.

 

05.10.2. Input limit

N is given in the first line. N is a natural number greater than or equal to 1 and less than or equal to 100.

 

05.10.3. Output

The first line prints the remainder of dividing the correct answer by 1,000,000,000.

 

05.10.4. Solution

dp table인 array a[i][j]를 i자리, j로 끝나는 수의 수라고 정의한다면 base case는 i=1일 때입니다.(자릿수가 1인 경우) 이때 첫 자릿수가 0인 경우는 없겠죠. 자릿수가 2이상인 경우에 대해 계산할 때는 몇 개의 case에 대해서만 다르게 계산된다는 점만 유의해주시면 됩니다.

	long long a[101][10], sum = 0;
	int i, j; 
	
	for(i = 1; i < 10; i++)
		a[1][i] = 1;
		
	for(i = 2; i <= n; i++){
		a[i][0] = a[i-1][1];
		a[i][9] = a[i-1][8];
		for(j = 1; j < 9; j++){
			a[i][j] = (a[i-1][j-1] + a[i-1][j+1]) % 1000000000;
		}
	}
	for(i = 0; i < 10; i++)
		sum = (sum + a[n][i]) % 1000000000;
	
	printf("%lld", n == 1? 9 : sum);

추가로 a[i][0]와 a[i][9]을 대입할 때는 이미 나머지 연산이 된 a[i-1][1]과 a[i-1][8]이 대입되기 때문에 굳이 나머지 연산을 해줄 필요가 없습니다. 최종적으로 자릿수가 n인 모든 경우를 다 합하여 출력해주면 됩니다. Top-down방식이라면 n과 digit가 DPfunction의 argument가 됩니다.