10844번 쉬운 계단 수

 

참조: https://www.youtube.com/watch?v=Rn9G6VrBKb4&t=621s

 

#include<iostream>

using namespace std;

int modular = 1000000000;
int main(void) {
	int n;
	cin >> n;
	long long arr[100][10];
	arr[0][0] = 0;
	for (int x = 1; x < 10; ++x) {
		arr[0][x] = 1;
	}
	for (int y = 1; y < n; ++y) {
		for (int x = 0; x < 10; ++x) {
			if (x == 0) {
				arr[y][x] = arr[y-1][1] % modular;
			}
			else if (x == 9) (arr[y][x] = arr[y - 1][8]) % modular;
			else {
				arr[y][x] = (arr[y - 1][x - 1] + arr[y - 1][x + 1]) % modular;
			}
		}
	}
	long long sum = 0;
	for (int x = 0; x < 10; ++x) {
		sum += arr[n - 1][x];
	}
	cout << sum % modular << endl;
}

 

자릿수 마지막의 값(행)&& 자릿수(열) 1 2 3	0	1	1
1	1	1	3
2	1	2	3
3	1	2	4
4	1	2	4
5	1	2	4
6	1	2	4
7	1	2	4
8	1	2	3
9	1	1	2

자릿수가 첫째자리 인경우 마지막 값이 0인 경우는 존재하지 않으니 0

마지막 값이 1 ~9는 각각 1개 씩 존재.

자릿수가 2개인 경우

10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 로

마지막값이 0인 경우는 1, 1인 경우는 21로 1나. 마지막값이 9인경우는 89 하나, 나머지 값들은 각 2개 씩 존재.

3 또한 동일한 방식으로 3개의 자릿수의 값에 마지막 값이 0 ~ 9로오는 갯수를 각각 구한다.

그러면 규칙이 보이는데 마지막 값이 0과 9를 제외하고는 나머지는 arr[y][x] = a[y-1][x-1] + a[y-1][x+1]이다. 마지막값이 0과9의 경우는 각각 이전 행의 1번째 열과 8번째 열을 그대로 사용한다.

고로 0과 9의 경우는 arr[y][0] = arr[y-1][1] , arr[y][9] = arr[y-1][8]이 된다.

초기에만 첫째자리가 1인 경우 0 번째 원소: 0 , 1~9 번째 원소 : 1 로 초기화해준다. 그 후 점화식을 통한 계산을 한다.

단, 오버플로우를 방지하기 위해 각 계산식에 modular 연산을 추가한다.