[BOJ] 1003 : 피보나치 함수

문제

[BOJ] 1003 : 피보나치 함수

해결

다이내믹 프로그래밍인줄 모르고 계속 시간초과떴다..

결국 메모이제이션!!!!!!!!!!!!!!을 하니까 맞았습니다><

코드

#include <stdio.h>
int mem[41];
int fibonacci(int n) {
    if (mem[n] > 0)
        return mem[n];
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    return mem[n] = fibonacci(n - 2) + fibonacci(n - 1);
}
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    for (int i = 0; i < testcase; ++i) {
        scanf("%d", &N);
        if (N == 0)
            printf("1 0\n");
        else
            printf("%d %d\n", fibonacci(N - 1), fibonacci(N));
    }
    return 0;
}