[백준] 9461번 - 파도반 수열 [C++]

---

문제

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

9461번: 파도반 수열

---

발상

위 그림을 순서대로 나열하면,

{1,1,1,2,2,3,4,5,7,9,12}가 된다.

이때, 규칙을 찾아보니 x = (x - 2) + (x - 3)이라는 조건을 찾게 되었고,

x-3의 값에 접근하기위해 값 3개를 미리 넣어두고 포문을 통해 100(문제의 최대범위)개를 넣은 뒤 찾고자 하는 값을 출력하게 하였다.

---

소스코드

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

int main()
{
	int testcase = 0,input;
	vector < long long > v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	for (int i = 4; i <= 100; i++)
	{
		v.push_back(v[i - 2] + v[i - 3]);
	}

	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		cin >> input;
		cout << v[input] << '\n';
	}
}