작업 저장소

Backjoon Online Judge 

"1003번 : 피보나치 함수" 문제입니다.

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

피보나치 함수를 구할 때 특정 함수가 몇번 호출되었는지 알기 위해서는 피보나치 함수를 재귀적으로 구현하여 함수 호출 될 때 마다 함수 호출 횟수를 1씩 증가시키면 됩니다. 하지만 그렇게 구현 할 경우 시간이 오래 걸리기 때문에 점화식을 구하여 쉽고 빠르게 함수 호출 횟수를 구했습니다.

위 표를 보면 fibo(0)의 호출 횟수와 fibo(1)의 호출 횟수도 피보나치 수의 증가와 같이 증가하는 것을 알 수 있습니다. (N = 0일때는 제외)

fibo(0) : 0 1 1 2 3 ...

fibo(1) : 1 1 2 3 5 ...

따라서 피보나치수를 배열을 이용해 빠르게 구하고 N의 값에 따라 그에 맞는 피보나치 수를 fibo(0), fibo(1)의 출력값으로 이용했습니다.

 - fibo(0)의 호출 횟수는 N이 주어질때 fibo(N-1)과 같습니다.

 - fibo(1)의 호출 횟수는 N이 주어질때 fibo(N)과 같습니다.

(표를 보고 규칙을 유추)

코드는 C++로 작성하였습니다.