(c++)백준 9461번: 파도반 수열

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

9461번: 파도반 수열

※점화식※

x = 0~4까지 초기화 해준다.

P[0] = 0

P[1] = 1

P[2] = 1

P[3] = 1

P[4] = 2

 

(x≥5) P[x] = P[x-1] + P[x-1-4]

* x= 6~8까지는 P[x-1-4] 가 아니라 P[1] ~ P[3] 순으로 더하지만 모두 1로 같으므로 위의 식을 쓸 수 있음

 

#include <iostream>
using namespace std;

int T;
int N;
long long P[101];
int cnt = 4;//어디까지 구했는지 알려줌

void DP() {
	P[0] = 0;
	P[1] = 1;
	if (N > 1) {
		P[2] = 1;
		P[3] = 1;
		P[4] = 2;
	}
	//이미 구한 값이라면
	if (N <= cnt) {
		cout << P[N] << endl;
		return;
	}
	for (int i = cnt + 1; i <= N; i++) {
		P[i] = P[i - 1] + P[i - 1 - 4];
	}
	cnt = N;
	cout << P[N] << endl;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> N;
		DP();
	}
	return 0;
}