[백준/BOJ] 백준 9461번 : 파도반 수열

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

9461번: 파도반 수열

n>=6일 때 P(n) = P(n-1) + P(n-5)라는 성질을 이용했다

 

코드

#include <iostream>
#include <cstring>
using namespace std;

long long cache[101];

long long Solve(int n)
{
	long long& ret = cache[n];

	//이미 값을 알고 있을때
	if (ret != -1)
		return ret;

	ret = Solve(n - 1) + Solve(n - 5);

	return ret;
}

void Pre()
{
	for (int i = 0; i < 101; i++)
		cache[i] = -1;

	cache[1] = 1;
	cache[2] = 1;
	cache[3] = 1;
	cache[4] = 2;
	cache[5] = 2;
}

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

	Pre();

	int t;
	int n;

	cin >> t;
	for (int tc = 0; tc < t; tc++)
	{
		cin >> n;
		cout << Solve(n) << "\n";
	}
	return 0;
}