백준 9461번: 파도반 수열

[문제 링크]

9461번: 파도반 수열

---

간단한 dp 문제였다.

파도반 수열에는 일정한 규칙이 있는데, 이를 점화식으로 표현하면 다음과 같다.

 

padovan(N) = padovan(N-2) + padovan(N-3)

 

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

long long memo[101];

long long Topdown(int N)
{
	if (N == 1) return 1;
	if (N == 2) return 1;
	if (N == 3) return 1;

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

	return ret = Topdown(N - 2) + Topdown(N - 3);
}

long long Bottomup(int N)
{
	memo[1] = memo[2] = memo[3] = 1;

	for (int i = 4; i <= N; i++)
		memo[i] = memo[i - 2] + memo[i - 3];
	
	return memo[N];
}

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

		// Top-down
		cout << "Top-down: " << Topdown(N) << endl;

		// Bottom-up
		cout << "Bottom-up: "<< Bottomup(N) << endl;
	}

	return 0;
}

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