[C++] 백준 9507번 Generations of Tribbles

다이나믹 프로그래밍 문제입니다.

피보나치에서 조금 응용된 형태입니다.
0 = 1
1 = 1
2 = 2
3 = 4
위와 같은 기본 값을 미리 입력하고

DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3] + DP[i - 4];

다음과 같은 방식으로 문제를 해결하였습니다.

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

long long int DP[10010];

int main(int argc, char *argv[]){
	int ts;
	int checkPoint = 3;

	cin >> ts;

	memset(DP, 0, sizeof(DP));

	DP[0] = 1;
	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;

	while (ts--) {
		int n;

		cin >> n;

		if(DP[n]){
			cout << DP[n] << endl;
			continue;
		}

		for (int i = checkPoint + 1; i <= n; ++i) {
			DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3] + DP[i - 4];
		}
		cout << DP[n] << endl;
		checkPoint = n;
	}

	return 0;
}