dp 백준 9461번 파도반 수열

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

9461번: 파도반 수열

파도반 수열은 삼각형을 나선 모양으로 놓여져 있다. 첫 삼각형은 변의 길이는 1입니다. 다음으로 계속해서 정삼각형을 추가합니다. 나선에서 가장 긴 변의 길이를 k인 정삼각형을 추가합니다. 아래와 같이 나선형 모형의 삼각형이 만들어 질 것입니다. 

 

P(N)은 나선에 있는 정삼각형의 변의 길이이다. 10개 숫자는 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 

 

이 문제를 해결하려면 위의 숫자들을 차례대로 써봤는데 피보나치 배열과 비슷한 패턴을 확인하여 점화식을 만들었습니다. 점화식을 통해 dp 방식으로 문제를 해결했습니다. 

#include <stdio.h>

int  testCase;

long long arr[102];
int numbers = 0;
int main(){
	scanf("%d", &testCase);

	arr[0] = 1;
	arr[1] = 1;
	arr[2] = 1;
	for(int i = 0; i < testCase; i++){
		scanf("%d", &numbers);

		for(int j = 3; j < numbers; j++)
			arr[j] = arr[j-3] + arr[j-2];
		

		printf("%lld\n", arr[numbers-1]);
	}
}