문제

문제 해결 전략

//1 1 1 2 2 3 4 5 7 9
//1 2 3 4 5 6 7 8 9 10

p(5) = p(0) + p(4)
p(6) = p(1) + p(5)
p(7) = p(2) + p(6)
p(8) = p(7) + p(3)
p(9) = p(8) + p(4)
p(10) = p(9) + p(5)

p가 파도반 수열이다.
점화식을 세워보면 p(n) = p(n-1) + p(n-5) 찾을 수 있다.

코드

//9461
#include <iostream>

using namespace std;
typedef long long ll;

ll dp[100000] = {
	0,
	1,
	1,
	1,
	2,
	2,
	3,
	4,
	5,
	7,
	9,
};

ll waveNum(int n)
{
	if (n <= 10) return dp[n];
	else if(dp[n]) return dp[n];
	else if (dp[n] == 0) return dp[n] = waveNum(n - 1) + waveNum(n - 5);
	return dp[n];
}
int main()
{
	int t; cin >> t;
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for (int i = t; i > 0; i--){
		int n; cin >> n;
		cout << waveNum(n) << '\n';
	}
}