1003번: 피보나치 함수

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


$O(t+N)$

dp1[i]: fibonacci(i)를 호출했을 때 출력되는 0의 개수
dp1[0]=1
dp1[1]=0
dp1[i]=dp1[i-1]+dp1[i-2]

dp2[i]: fibonacci(i)를 호출했을 때 출력되는 1의 개수
dp2[0]=0
dp2[1]=1
dp2[i]=dp2[i-1]+dp2[i-2]

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