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

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

10844번: 쉬운 계단 수

백준 10844번 쉬운 계단 수를 풀어봤습니다.

동적계획법 문제이고 bottom-up, top-down 두 가지 방식으로 풀 수 있습니다.

 

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define MOD 1000000000

int N;
int arr[100][10];

int dp(int n, int k) {
	if (k < 0 || k>9)
		return 0;

	if (arr[n][k] != 0)
		return arr[n][k];

	if (n == 0) {
		if (k == 0)
			return 0;
		else {
			arr[0][k] = 1;
			return arr[0][k];
		}
	}

	arr[n][k] = dp(n - 1, k - 1) % MOD + dp(n - 1, k + 1) % MOD;
	return arr[n][k];
}

int main() {
	cin >> N;
	long long result = 0;
	for (int i = 0; i < 10; i++) {
		result += dp(N - 1, i);
	}

	cout << result % MOD;

	return 0;
}