[백준] 10844번 쉬운 계단 수

10844번: 쉬운 계단 수

   N값에 따른 계단의 수를 3까지 나타내 보면

 

i / j	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
2	10 12	21 23	32 34	43 45	54 56	65 67	76 78	87 89	98
3	101 121 123	210 212 232 234	321 323 343 345	432 434 454 456	543 545 565 567	654 656 676 678	765 767 787 789	876 878 898	987 989

 

1번째 일 때는

[i][1] = [i-1][j+1] + [i-2][1]

 

2번째부터 9번째까지는

[i][2]~[i][9] = [i-1][j+1] + [i-1][j-1]

 

이런 형태를 나타낸다.

이대로 구현해주면 된다.

 

#include <iostream>
using namespace std;
int res[101][10] = { 0 };

int main() {
	int N;
	cin >> N;

	for (int i = 1; i < 10; i++) {
		res[1][i] = 1;
		res[2][i] = 2;
	}
	res[2][9] = 1;

	for (int i = 3; i <= N; i++) {
		for (int j = 1; j < 10; j++) {
			if (j == 1) res[i][j] = (res[i - 1][j + 1] + res[i - 2][j]) % 1000000000;
			else res[i][j] = (res[i - 1][j + 1] + res[i - 1][j - 1]) % 1000000000;
		}
	}

	int sum = 0;
	for (int i = 1; i < 10; i++) sum += res[N][i] % 1000000000;
	cout << sum;

	return 0;
}