BOJ 1003 피보나치 함수

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

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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

---

주어진 소스코드대로 재귀를 사용하면 당연히 시간 초과가 걸린다.

적당히 테스트해보면 결과값은 n-1, n이 된다는 것을 발견할 수 있다.

따라서 n-1, n을 출력해주면 된다.

0번째의 n-1도 출력해주기 위해서 배열을 +1씩^[각주:1] 해주었고 0번째 칸에는 1을 삽입했다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

// 1003 피보나치 함수 #include<stdio.h> #define FOR(i,j) for(int i=3;i<=j;i++) int main() { int T, n; int fibo[46] = { 1, 0, 1 }; scanf("%d", &T); while (T--) { scanf("%d", &n); FOR(i, n+1) fibo[i] = fibo[i - 1] + fibo[i - 2]; printf("%d %d\n", fibo[n], fibo[n + 1]); } return 0; }

1. 즉 n, n+1을 출력해주었다. [본문으로]