[acmicpc.net] 1003 피보나치 함수

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

소스코드

fibo = [[1, 0], [0, 1]]
 
def fibonacci(N, res):
    for i in range(N):
        if i<len(res):
            continue
        res.append([res[i-2][0]+res[i-1][0], res[i-2][1]+res[i-1][1]])
    return res
 
fibonacci(41, fibo)
 
T = int(raw_input(""))
 
for i in range(T):
    N = int(raw_input(""))
    res = fibo[N]
    print(str(res[0])+" "+str(res[1]))