[C/C++] 백준 - 10844번 : 쉬운 계단 수

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

10844번: 쉬운 계단 수

점화식을 찾는 DP문제

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define swap(type,x,y) do{type t=x; x=y;y=t;} while(0)
#define mod 1000000000

using namespace std;

long long dp[101][11];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	dp[1][0] = 0;
	for (int i = 1; i <= 9; i++) dp[1][i] = 1;

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

	long long sum = 0;
	for (int i = 0; i <= 9; i++) {
		sum += dp[N][i];
	}
	cout << sum % mod << '\n';

	return 0;
}