백준 9507번: Generations of Tribbles

[문제 링크]

9507번: Generations of Tribbles

---

파보나치 수열 유형의 간단한 dp 문제였다. 문제에 제시된 조건대로 함수를 구현하면 된다.

---

#include <iostream>
using namespace std;

long long memo[67];

long long Topdown(int n)
{
	if (n < 2) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;

	long long& ret = memo[n];
	if (ret != 0) return ret;

	return ret = Topdown(n - 1) + Topdown(n - 2) + Topdown(n - 3) + Topdown(n - 4);
}

long long Bottomup(int n)
{
	memo[0] = memo[1] = 1;
	memo[2] = 2, memo[3] = 4;

	for (int i = 4; i <= n; i++)
		memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3] + memo[i - 4];

	return memo[n];
}

int main(void)
{
	int tc;
	cin >> tc;
	
	while (tc--)
	{
		int n;
		cin >> n;

		cout << Topdown(n) << endl;

		cout << Bottomup(n) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 101 day