[백준 1003] 피보나치 함수

1003번 : 피보나치 함수

1003: 피보나치 함수

방법 1 (틀림)

• 문제에 주어진 함수를 그대로 구현하는 것은 비효율적 (재귀함수로만 구현하게 되면 이미 구해놓은 정보를 다시 구해야하므로 비효율적)

import sys
input = sys.stdin.readline


def fibonacci(n, result):
    if n == 0:
        result[0] += 1
    elif n == 1:
        result[1] += 1
    else:
        fibonacci(n-1, result)
        fibonacci(n-2, result)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n = int(input())
        result = [0, 0]
        fibonacci(n, result)
        print(*result)

방법 2 (옳은 풀이)

• 피보나치 함수
  • n == 0인 경우 : f(0) = f(0)
  • n == 1인 경우 : f(1) = f(1)
  • n >=2 인 경우 : f(n) = f(n-1) + f(n-2)

import sys
input = sys.stdin.readline


def fibonacci(n):
    length_zero = len(zero)
    # 피보나치 수열로 더 표현할 수 있는 경우
    if n >= length_zero:
        for i in range(length_zero, n+1):
            # f(n) = f(n-1) + f(n-2)
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print(f"{zero[n]} {one[n]}")

if __name__ == '__main__':
    t = int(input())

    # f(0) = f(0)
    # f(1) = f(1)
    # f(2) = f(1) + f(0) <- 2부터 규칙 적용
    zero = [1, 0, 1]
    one = [0, 1, 1]
    for _ in range(t):
        fibonacci(int(input()))