[C++] 백준 1003 : 피보나치 함수

#include <iostream>

int dp1[41] = {0};
int dp2[41] = {0};

void fibonacci() { // 그대로 쓰면 시간 초과
    dp1[0] = 1; dp1[1] = 0;
    dp2[0] = 0; dp2[1] = 1;
    
    for (int i = 2; i <= 41; i++){
        dp1[i] = dp1[i-2] + dp1[i-1];
        dp2[i] = dp2[i-2] + dp2[i-1];
    }
}

int main(int argc, char **argv){
    int T, N;
    scanf("%d",&T);
    fibonacci();

    for (int i=0; i<T; i++){
        scanf("%d", &N);
        printf("%d %d\n", dp1[N], dp2[N]);
    }

    return 0;
}

오늘의 키포인트

• 그대로 주어진 함수를 사용하면 시간초과
• 0 : 0 / 1 : 1 / 2 : 0 1 / 3 : 0 1 1 / 4 : 0 0 1 1 1
  이런 형태로 앞의 호출한 횟수만큼 더한 것과 같다.