[백준 1003] 피보나치 함수 with Python

문제 링크

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

풀이

import sys

t = int(sys.stdin.readline())
dp = [(1, 0), (0, 1)]

for i in range(t):
    n = int(sys.stdin.readline())
    for i in range(len(dp), n+1):
        dp.append((dp[i-1][0]+dp[i-2][0], dp[i-1][1]+dp[i-2][1]))
    print(dp[n][0], dp[n][1])

f(n) = f(n-1) + f(n-2)이므로, f(n)을 수행하는 동안 0과 1을 출력한 횟수는 f(n-1)과 f(n-2)를 각각 수행하는 동안 0과 1을 출력한 횟수의 합과 같다. 예를 들어 f(2)에서 1을 한 번 출력하고, f(1)에서는 0을 한 번 출력 하였으므로, f(3)에서는 0과 1을 모두 한 번씩 출력하게 된다. 그러므로 dp[2]는 (1, 1)이 된다.

 

외부 for문 내부에 있는 for문은 dp의 길이가 n보다 작거나 같을 때에만 실행되며, dp의 길이가 n+1이 될 때까지 값을 채워넣는다. 최종적으로 dp의 길이는 n으로 입력받은 수 중에서 최댓값+1이 된다.

 

 

import sys

t = int(sys.stdin.readline())
memo = [0, 1]
zero_one = [(1, 0), (0, 1)]
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        zero = 0
        one = 0
        if len(memo) <= n:
            nth = fibonacci(n-1) + fibonacci(n-2)
            memo.append(nth)
            zero += zero_one[n-1][0] + zero_one[n-2][0]
            one += zero_one[n-1][1] + zero_one[n-2][1]
            zero_one.append((zero, one))
        else:
            nth = memo[n-1] + memo[n-2]
            
        return nth

for i in range(t):
    n = int(sys.stdin.readline())
    fibonacci(n)
    print(zero_one[n][0], zero_one[n][1])

처음에는 피보나치 함수를 구현하여 통과하였다. 위에 있는 코드와 메모리나 시간은 동일하게 뜬다.