[BAEKJOON 1003] 피보나치 함수

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

문제: 피보나치 함수에서 0, 1이 호출되는 횟수를 구하여라.

 

제약 조건: 입력하는 숫자는 40이하의 자연수이다.

 

---

별 생각 없이 문제에 주어진 fibonacci 함수를 그대로 넣고 0, 1일때 카운트를 했더니 타임아웃이 났다.

피보나치 함수는 매번 나오는 말이지만, 재귀를 얼마나 효율적으로 축소할 수 있는가 를 따지는, DP의 입문격인 문제이다.

그러니 타임아웃이 나는걸 당연하게 생각하고 다시 접근해 봤다.

 

피보나치 함수는 f(n) = f(n-1)+ f(n-2) 이고, f(n)이 0, 1 이 아닌 경우에 f(n-1), f(n-2)의 0, 1의 합이다.

따라서, 다음과 같이 정리된다.

 

	0	1
0	1	0	0 고정
1	0	1	1 고정
2	1	1	f(2) = f(0) + f(1)
3	1	2	f(3) = f(1) + f(2)
4	2	3	f(4) = f(2) + f(3)
5	3	5	f(5) = f(3) + f(4)

그러니 반대로 0에서 40까지에 대한 0의 개수, 1의 개수를 미리 계산해 두고 접근을 해서 풀었다.

 

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <iostream>
#include <set>
using namespace std;

int hash0[41];
int hash1[41];


void cheat() {
    hash0[0] = 1;
    hash1[0] = 0;
    hash0[1] = 0;
    hash1[1] = 1;
    for (register int i = 2; i < 41; i++) {
        hash0[i] = hash0[i - 1] + hash0[i - 2];
        hash1[i] = hash1[i - 1] + hash1[i - 2];
    }

}

int main() {
    int a, n;
    cin >> a;
    cheat();
    for (register int i = 0; i < a; i++) {
        cin >> n;
        cout << hash0[n] << " " << hash1[n] << endl;

    }
	return 0;
}