#10844번 쉬운 계단 수 (C++)

링크 : www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

매우 어려운 논리를 요구하는 DP문제는 아니였다. 

하지만 Over flow를 방지하기 위해 계산마다 1,000,000,000을 나눠주는 점을 놓쳐서 오답이 나와버렸다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

long long int arr[101][11];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long int ans = 0;
	int n = 0;
	cin >> n;
	for (int i = 1; i < 10; i++) arr[1][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) arr[i][0] = arr[i - 1][1];
			else arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]) % 1000000000;
		}
	}
	for (int i = 0; i <= 9; i++) {
		ans += arr[n][i];
	}
	cout << ans % 1000000000<< "\n";
	return 0;
}