백준-쉬운 계단수.cpp.txt

#include<iostream>
#include<stdlib.h>
#include<queue>
#include<string>
#include<cstring>
#define mod 1000000000

using namespace std;
int **arr;

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

	arr = new int*[N+1]();
	
	for (int i = 0; i <= N; i++)
	{
		arr[i] = new int[10]();
	}

	for (int i = 1; i <= 9; i++)
		arr[1][i] = 1;
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			arr[i][j] = 0;
			if (j - 1 >= 0)
				arr[i][j] += arr[i - 1][j - 1];
			if (j + 1 <= 9)
				arr[i][j] += arr[i - 1][j + 1];
			arr[i][j] %= mod;
		}
	}

	long long ans = 0;
	for (int i = 0; i < 10; i++)
		ans += arr[N][i];
	ans %= mod;
	cout << ans << endl;
	
	return 0;


}