백준 10844 쉬운계단수 c++ // dp

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

10844번: 쉬운 계단 수

1. 의사코드

1. 규칙발견 && 테이블정의 :  dp [길이][끝나는숫자] 의 갯수

아래숫자 == 위행의 좌측 + 위행의 우측 이다.

 

2. 주의사항

%1억할때, (a%1억 + b%1억) %1억해야 올바른 값이 나온다..

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll d[104][12]; //오큰수의 갯수 [길이][시작숫자]
ll n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for (int j = 2; j <= 10; ++j) d[1][j] = 1;

	for (int i = 2; i <= 100; ++i) {
		for (int j = 1; j <= 10; ++j) {
			d[i][j] = (d[i-1][j-1] % 1000000000 +d[i-1][j+1] % 1000000000)%1000000000;
		}
	}

	ll ret = 0;
	for (int j = 0; j <= 10; ++j) ret = (ret % 1000000000 + d[n][j] % 1000000000)% 1000000000;
	cout << ret;

	return 0;
}