[백준 9461] 파도반 수열

분류 

dp

요구사항

파도반 수열 구하기

 

풀이

파도반 수열은

1 1 1 2 2 3 4 5 7 9 .... 이런식으로 이루어져있다.

이는 d[n]=d[n-2]+d[n-3]으로 표현된다.

점화식만 찾는다면 쉬운 문제

long long 주의

 

#include <iostream>

using namespace std;
long long d[110];
int n;
int main() {
	int t;
	scanf("%d", &t);
	d[1] = 1;
	d[2] = 1;
	d[3] = 1;
	for (int i = 4; i <= 100; i++) {
		d[i] = d[i - 2] + d[i - 3];
	}
	for (int i = 0; i < t; i++) {
		scanf("%d", &n);
		printf("%lld\n", d[n]);
	}
	//cout << d[n] << endl;
}