[백준] 9461파도반수열 c++

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

9461번: 파도반 수열

수열을 보고 규칙을 찾았을 때는 이 식을 찾았다.   P(i)=P(i-2)+P(i-3)  (단,i>3)

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16....

그림을 보면  i번째 삼각형의 한변의 길이는 P(i-1)+P(i-5)임을 알 수 있다.

 

나는 첫번째 점화식으로 풀었다.

그리고 1~100 까지 P(i)를 출력해보니까 오버플로우가 일어나서 배열을 int 에서 long long으로 바꾸어 주었다.

#include<iostream>

using namespace std;

int main()
{
	int T,N; //1<=N<=100
	long long num[101];
	cin >> T;
	
	num[1] = 1;
	num[2] = 1;
	num[3] = 1;
	num[4] = 2;
	num[5] = 2;
	for (int i = 6; i <= 100; i++)
	{
		num[i] = num[i - 2] + num[i - 3];
		//cout << num[i] << endl;
	}
	while (T--)
	{
		cin >> N;
		cout << num[N] << "\n";
	}
}