[210529][백준/BOJ] 9461번 파도반 수열

문제

입출력

풀이

정삼각형의 변의 길이를 나열하면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ... 이다.

여기서 1+1=2, 1+1=2, 1+2=3, 2+2=4, 2+3=5, 3+4=7, 4+5=9, ... 인 규칙을 찾을수있다.
d[i]는 두번째 전과 세번째 전의 값을 합친 값이며 이를 점화식으로 나타내면 다음과 같다.

d[i] = d[i-2] + d[i-3]

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll d[102];

ll dp(int n)
{
	d[1] = 1;
	d[2] = 1;
	d[3] = 1;

	for (int i = 4; i <= n; ++i)
		d[i] = d[i - 2] + d[i - 3];
	return d[n];
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;

	while (t--)
	{
		int n;
		cin >> n;

		cout << dp(n) << '\n';
	}
}