[BOJ] 1003 : 피보나치 함수 (Python3)

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

문제

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=0일 때 0이 1번 출력된다.
N=1일 때 1이 1번 출력된다.
N=2일 때 fibonacci(0) 호출회수 + fibonacci(1)이 호출회수, 0이 1번, 1이 1번 출력된다.
N=3일 때 fibonacci(1) 호출회수 + fibonacci(2)가 호출회수, 0이 1번, 1이 2번 출력된다.

여기서 알 수 있는 것은, 피보나치 함수의 호출 회수도 피보나치 수열을 따르고 있다는 것이다.
그러므로 이를 해결하기 위해서는 0과 1의 호출 회수를 따로 배열에 저장한 뒤, 반복문으로 피보나치 수열을 만들어야 한다.

소스코드

import sys
input = sys.stdin.readline

t = int(input())
f0 = [1, 0]  # f0[n] 은 fibonacci(n)에서 0이 출력된 횟수
f1 = [0, 1]

def cal(n):
	length = len(f0)
	if n >= length:
		for i in range(length, n+1):
			f0.append(f0[i-1] + f0[i-2])
			f1.append(f1[i-1] + f1[i-2])
	print(f0[n], f1[n])

for i in range(t):
	n = int(input())
	cal(n)