[9461] 파도반 수열

이 문제는 파보나치 수열과 비슷해서 매우 쉬웠다.

정답값이 int범위를 넘어가서 한번 틀려서 long long으로 고쳤다.

이제까지와는 달리 탑다운 방식으로 풀어보았다.

#include <cstdio>
using namespace std;
​
long long d[101];
long long padoban(long long n)
{
    if (n < 3) 
        return 1;
    if (d[n] != -1) //이미 계산한것이면 d[n]을 바로 리턴
        return d[n];
​
    d[n] = padoban(n - 2) + padoban(n - 3); //계산 안된것이면 계산해서 리턴
​
    return d[n];
}
​
int main()
{
    int T;
    scanf("%d", &T);
    int *res = new int[T];
​
    for (int i = 0; i < T; i++)
    {
        scanf("%d", &res[i]);
    }
    for (int i = 0; i < T; i++)
    {
        for (int j = 0; j < 102; j++)
        {
            d[j] = -1;
        }
        printf("%lld\n",padoban(res[i]-1));
    }
}