백준(BOJ) 1003번 피보나치 함수

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

나의풀이:

f(0)의 0과 1의 수 :  1 0

f(1)의 0과 1의 수 :  0 1

f(2)의 0과 1의 수 :  1 1

f(3)의 0과 1의 수 :  1 2

f(4)의 0과 1의 수 :  2 3

f(5)의 0과 1의 수 :  3 5     

f(n) 은 f(n-2) + f(n-1) 를 세로로 각각 더해주면 나온다는 것을 알 수 있다.

그림에 보듯 f(n)의 0의수는 f(n-1)의 1의 수와 똑같기에 f(n)들의 1의 수 값을 구해보자

f(n)의 1의 수는 일반 피보나치와 똑같음으로(0 1 1 2 3 5 ... )  n에서의 피보나치를 구한후 n-1 피보나치와 (0의 수) 함께 출력해주면 되겠다

코드 ( C ++ )

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

int N;

int cache[41];

int fibonacci(int n) // 피보나치를 구한다.

{

if (n == 0)

return 0;

if (n == 1)

return 1;

int& ret = cache[n];

if (ret != -1)

return ret;

return ret = fibonacci(n - 1) + fibonacci(n - 2);

}

int main()

{

int C;

cin >> C;

while (C--) {

memset(cache, -1, sizeof(cache));

int N;

cin >> N;

if (N == 0) {  // f(0)의 0의값과 1의값은 구할수 없으므로 따로 처리해준다. 

cout << 1 << " " << 0 << endl;

continue;

}

int ans = fibonacci(N);  // fibonacci(N)을 구한다. 즉 1의 수가 된다

int ans2 = fibonacci(N - 1);  // fibonacci(N-1)을 구한다 0의 수가 된다.

cout << ans2 << " " << ans << endl;

}

return 0;

}