백준 1003 피보나치 함수

<Bottom-Up> 방식

n은 최대 40까지이므로 for문을 돌려 40까지의 답을 구해 놓은 후 풀었다.

#include <cstdio>
using namespace std;
 
int d[41][2];
 
int main() {
    d[0][0] = d[1][1] = 1;
    d[0][1] = d[1][0] = 0;
 
    for (int i = 2; i <= 40; i++) {
        d[i][0] = d[i - 1][0] + d[i - 2][0];
        d[i][1] = d[i - 1][1] + d[i - 2][1];
    }
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%d %d\n", d[n][0], d[n][1]);
    }
    return 0;
}
 

<Top-Down 방식>

규칙을 잘 살펴보면 n일 때의 0의 갯수는 n-1일 때의 1의 갯수와 같다.

#include <cstdio>
using namespace std;
 
int d[41];
 
int fibonacci(int n) {
    if (d[n] > 0) return d[n];
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else {
        return d[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }
}
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 0) printf("1 0\n");
        else printf("%d %d\n", fibonacci(n-1), fibonacci(n));
    }
    return 0;
}