문제

풀이

피보나치 함수를 재귀함수로 호출할 때 0과 1이 각각 몇 번 출력되는지 구하는 문제이다. 재귀함수를 많이 호출하게 되면 같은 함수를 여러 번 호출하게 되서 비효율적이고 메모리 초과가 된다. 그렇기 때문에 다이나믹 프로그래밍을 이용하여 풀어야 한다.

n=0일 때 0은 1번 출력, 1은 0번 출력
n=1일 때 0은 0번 출력, 1은 1번 출력
n=2일 때 fibonaci(2) = fibonaci(1) + fibonaci(0)
이므로 0은 1번 출력, 1은 1번 출력
n=3일 때 fibonaci(3) = fibonaci(2) + fibonaci(1)
fibonaci(3) = fibonaci(1) + fibonaci(1) + fibonaci(0)

표로 정리하면 다음과 같다.

n	0	1	2	3	4	5
0 호출 횟수	1	0	1	1	2	3
1 호출 횟수	0	1	1	2	3	5

표에서 규칙성을 찾을 수 있는데 n=2부터 적용되는 점화식을 구할 수 있다. fibonaci(n) = fibonaci(n-1) fibonaci(n-2) (n>=2) n의 0과 1의 호출 횟수는 n-1과 n-2의 호출 횟수의 합과 같다.

import sys

def input():
    return sys.stdin.readline().rstrip()

f0 = [0] * 41
f1 = [0] * 41

t = int(input())

f0[0] = 1
f1[1] = 1

for _ in range(t):
    n = int(input())
    for i in range(2, n+1):
        if f0[i] == 0 and f1[i] == 0:
            f0[i] = f0[i-1] + f0[i-2]
            f1[i] = f1[i-1] + f1[i-2]
    print(f0[n], f1[n])