백준 22.02.01. 1003번 - 피보나치 함수

T = int(input())

zero = [1, 0, 1]
one = [0, 1, 1]


def Fibonacci(n):
    if n >= len(zero):
        for i in range(len(zero), n + 1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print('{} {}'.format(zero[n], one[n]))


for i in range(T):
    Fibonacci(int(input()))

• 주어진 횟수만큼 피보나치를 실행했을 때 0과 1이 얼마만큼 호출되는지 구하는 문제입니다.
• 따라서 0과 1얼마나 호출되는지 규칙을 찾아봅니다.

• 	0	1	2	3	4	5
  0	1	0	1	1	2	3
  1	0	1	1	2	3	5

  • 피보나치함수에 주어진 수가 2보다 작다면 미리 준비된 수열이 없으므로 0일땐 0, 1일땐 1을 반환합니다.
  • 그리고 2 이상이라면 Fibonacci(2) = Fibonacci(1) + Fibonacci(0) 이기때문에
    • 0이 호출되는 횟수는 zero = 1 + 0
    • 1이 호출되는 횟수는 one = 0 + 1
  • 과 같이 나오며 Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = Fibonacci(1) * 2 + Fibonacci(0) 이 됩니다.
    • 따라서 zero = 0*2 + 1, one = 1*2 + 0 입니다.
  • 마찬가지로 Fibonacci(4) = Fibonacci(3) + Fibonacci(2) = Fibonacci(2)*2 + Fibonacci(1) = Fibonacci(1) * 3 + Fibonacci(0) * 2 입니다.
    • 따라서 zero = 0*3 + 1*2, one = 1*3 + 0*2입니다
  • 이렇듯이 0과 1이 호출되는 횟수도 피보나치수열로 증가하는 것을 확인할 수 있습니다.
    • 하지만 zero = Fibonacci(n-1), one = Fibonacci(n)같은 식으로 실행한다면 재귀함수를 사용하기때문에 시간초과가 나옵니다.
• 우선 zero와 one의 패턴을 미리 만들어둡니다.
• 이어서 입력받은 수가 zero의 길이보다 길다면 반복문으로 모자란 피보나치 수열을 추가해줍니다.
• 이 후 zero패턴의 n번째 값과 one패턴의 n번째 값을 출력해주면 됩니다.