백준9461 - 파도반 수열

 

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

9461번: 파도반 수열

DP문제이다.

수열의 5번째 항까지 규칙이 적용되지 않은채 정해진 값이 들어간다.

수열의 6번째 항부터는 바로 전번째 항 더하기 구하려는 항으로 부터 5번째 뒤에 있는 항을 더한다.

#include <iostream>
using namespace std;

long long int mat[101]; //수열의 항이 어느정도 커질지 모르기 때문에 long long int 선언

int main() {

	int T; //입력할 갯수
    
    
    //5번째 항까지 숫자를 정해 놓는다.
	mat[1] = 1;
	mat[2] = 1;
	mat[3] = 1;
	mat[4] = 2;
	mat[5] = 2;
    
    //6번째 항부터 100번째 항까지 파도반 수열을 구한다.
	for (int i = 6; i <= 100; i++) {
		mat[i] = mat[i - 1] + mat[i - 5];
	}
    
    
	cin >> T;
	while (T--) { //T번 반복
		int a;
		cin >> a;
		cout << mat[a] << '\n'; //입력한 숫자의 해당 dp값을 출력해 준다.
	}
}