[백준 10844] 쉬운 계단 수

분류 : DP

 

요구사항

쉬운 계단의 숫자 구하기

인접한 숫자의 차이가 1인 수 구하기

 

풀이

손으로 2~3까지 적다보면 점화식이 보인다

1자리는 9개

1자리의 쉬운 계단 수에다가 -1, +1를 더한 값이다

이를 점화식으로 나타내면

d[i][j] = d[i-1][j-1] +d[i-1][j+1]이다

하지만 0과 9일때는 예외 처리해준다

 

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int d[110][10];
int main() {
	scanf("%d", &n);
	d[1][0] = 1;
	for (int i = 1; i <= 9; i++) d[1][i] = 1;

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 9) d[i][j] = (d[i - 1][j - 1]) % 1000000000;
			else if (j == 0) d[i][j] = d[i - 1][1] % 1000000000;
			else d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % 1000000000;
		}
	}
	int ans = 0;
	for (int i = 1; i <= 9; i++) {
		ans = (ans + d[n][i]) % 1000000000;
	}
	cout << ans << endl;
}