백준 1003번: 피보나치 함수 (Python)

접근

단순 재귀함수로 풀었을 때 피보나치 수를 구하기 위해 많은 시간이 걸린다고 한다. 당연하게도 그냥 피보나치 수를 구하는 재귀함수에 n = 0, n = 1일때마다 카운트하게 코드를 작성하면 시간 초과가 되게 된다.

def fibonacci(n):
    global fibonacci_count

    if n == 0:
        fibonacci_count[0] += 1
        return 0
    elif n == 1:
        fibonacci_count[1] += 1
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

요점은 n번째 피보나치 수는 n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이라는 것이다. 즉 n번째 피보나치 수가 0과 1을 호출하는 횟수는 n-1번째 수와 n-2번째 피보나치 수의 0과 1 호출 수의 합이다. list를 하나 작성하여 n번째 피보나치 수가 list의 n번째 요소에서 [0 호출 횟수, 1 호출 횟수]를 값으로 갖도록 작성하고, 이후 fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)를 이용하여 요소를 채우면 빠른 시간 안에 n번째 피보나치 수의 0, 1 호출 수를 계산할 수 있다.

코드

import sys


fibonacci = []
fibonacci.append([1, 0])  # 0번째 요소는 0을 1번 호출
fibonacci.append([0, 1])  # 1번째 요소는 1을 1번 호출

n = int(sys.stdin.readline())
for i in range(n):
    m = int(sys.stdin.readline())
    for j in range(m + 1):
        if j < len(fibonacci):
            continue
        x = fibonacci[j - 1][0] + fibonacci[j - 2][0]
        y = fibonacci[j - 1][1] + fibonacci[j - 2][1]
        fibonacci.append([x, y])
    print('{} {}'.format(fibonacci[m][0], fibonacci[m][1]))

더 생각해 볼 것?

...