[백준] 알고리즘 1003번 - 피보나치 함수 문제

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1 2 3 4 5 6 7 8 9 10 11

int fibonacci(int n) {     if (n == 0) {         printf("0");         return 0;     } else if (n == 1) {         printf("1");         return 1;     } else {         return fibonacci(n‐1) + fibonacci(n‐2);     } }

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[41];
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int T;
   cin >> T;
   dp[0] = 0, dp[1] = 1, dp[2] = 1;
   for (int i = 3; i <= 40; i++) dp[i] = dp[i - 2] + dp[i - 1];
   while (T--) {
	   int n;
	   cin >> n;
	   if (n == 0) cout << "1 0";
	   else if (n == 1) cout << "0 1";
	   else cout << dp[n - 1] << " " << dp[n];
	   cout << "\n";
   }
}

풀이

피보나치 4까지만 해봐도 대충 규칙이 있다는 것을 알 수 있습니다.

우선 구해야하는건 fb(1)과 fb(0)이 나타나는 개수를 출력하는 건데요.

      0      1       2       3     4

fb   0       1      1       2     3

0    1       0      1       1     2

1    0       1      1       2     3

 

fb(0)은 자기 라인의 피보나치를 이루고 있고

fb(1)도 마찬가지로 자기 라인의 피보나치를 이루고 있다.

 

즉 n에 따라 0은 n의 피보나치 수 - 1 

1은 n의 피보나치와 같으므로

 

출력을 dp[n-1] dp[n] 을 해주면 됩니다.