[백준]Baekjoon9461(Dynamic Programming)

문제 링크 : https://www.acmicpc.net/problem/9461

정말 단순하게 규칙만 찾으면 풀 수 있는 문제이다.

길이가 memo배열에 할당시켰다고 했을 때

수를 쭉 나열해서 살펴보면 memo[i] = memo[i-1] + memo[i-5] 임을 알 수 있으며

이를 통해 memo[N]을 구하면 된다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

long long memo[101];
int main()
{
	memo[1] = 1; memo[2] = 1; memo[3] = 1; 
	memo[4] = 2; memo[5] = 2;
	int T;	int N;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		for (int i = 6; i <= N; i++) {
			memo[i] = memo[i - 1] + memo[i - 5];
		}
		printf("%lld\n", memo[N]);
	}
}