4일차

 

#include <stdio.h>

int Num[41];           //N은 40보다 작거나 같은 자연수 또는 0이다.

int fibonacci(int n)
{
    if(n <= 0)
    {
        Num[0] = 0;
        return 0;
    }
    
    else if(n ==1)
    {
        Num[1] = 1;
        return 1;
    }
    
    if(Num[n] != 0)
    {     
        return Num[n];
    } 
    
    else 
    {
        return Num[n] = fibonacci(n-1) + fibonacci(n-2);
    }
}

int main(void)
{
    int test;
    scanf("%d", &test);
    while(test-- > 0)
    {
        int input;
        scanf("%d", &input);
        
        if(input == 0)
        {
            printf("%d %d\n", 1, 0);
        }
        else if(input == 1)
        {
            printf("%d %d\n", 0, 1);
        }
        else
        {
            fibonacci(input);
            printf("%d %d\n", Num[input-1], Num[input]);
        }
    }
    return 0;
}

그냥 피보나치 문제