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

블로그에 올리는 모든 문제 풀이는 깃허브에 올려져 있습니다.

---

문제 설명

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

  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(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
  첫째 줄에 테스트 케이스 T가 주어진다.
  각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
  각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

풀이 전략

• n에 대해서 fibonacci(n)을 실행시켰을 때 fibonacci(0)과 fibonacci(1)이 불리는 횟수를 구하는 것이다.
• 매번 재귀 함수를 호출해서 수를 구한다면 시간 초과가 나므로 규칙성을 찾아야 한다.
  
• 찾은 규칙은 다음과 같다.
  

  N	zero	one
  0	1	0
  1	0	1
  2	1	1
  3	1	2
  4	2	3
  5	3	5
  6	5	8
  7	8	13

• 즉, 0의 출력 횟수는 dp [n-1], 1의 출력 횟수는 dp [n]과 같다.
• 그리고 dp [n] = dp [n-1] + dp [n-2]와 같다.

소스 코드

#include <iostream>

using namespace std;
int main()
{
	int n;
	int dp[41] = { 0, 1, 1 };
	for (int i = 3; i < 41; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		if (x == 0)
			cout << 1 << ' ' << 0 << '\n';
		else if (x == 1)
			cout << 0 << ' ' << 1 << '\n';
		else
			cout << dp[x-1] << ' ' << dp[x] << '\n';
	}
}

---

링크

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

1003번: 피보나치 함수