[백준]Baekjoon9095(Dynamic Programming)

풀이

기저조건 : 기본 조건인 n = 1, 2, 3 일때 나오는 가짓수는

memo[1] = 1 // 1

memo[2] = 2 // 1+1 , 2

memo[3] = 4 // 1+1+1, 1+2, 2+1, 3

점화식 : n번째 문자를 나타내는 경우의 수는 n-1일 때의 경우에서 1을 붙이는 경우,

n-2의 경우에서 2를 붙이는 경우, n-3의 경우에서 3을 붙이는 경우가 있다.

고로 f(n) = f(n-3) + f(n-2) + f(n-1)이다.

#include <iostream>

using namespace std;

int memo[11];
int main()
{
	int n; int testcase;
	cin >> testcase;
	memo[1] = 1; memo[2] = 2; memo[3] = 4;

	while (testcase--) {
		cin >> n;
		for (int i = 4; i <= n; i++)
			memo[i] = memo[i - 3] + memo[i - 2] + memo[i - 1];

		cout << memo[n] << '\n';
	}
}