[python] 1003. 피보나치 함수

문제 출처

1003. 피보나치 함수

 

풀이

피보나치를 재귀로 짰을때 0과 1이 리턴되는 횟수를 구하는 문제이다. 이 문제를 처음에는 재귀로 풀었는데 시간 복잡도 O(2^N)으로 시간 초과가 났다. 시간을 줄이기 위해 재귀가 아닌 for문을 이용해 이 전에 계산한 결과를 저장해 다음 결과를 도출하는 DP로 풀었더니 시간복잡도가 O(N)이 나왔다.

 

재귀 코드(시간초과)

 

def fib(n):
    global zero, one
    if n == 0:
        zero += 1
        return 0
    elif n == 1:
        one += 1
        return 1
    else:
        return fib(n-1) + fib(n-2)

tc = int(input())
for _ in range(tc):
    n = int(input())
    zero, one = 0, 0
    fib(n)
    print(zero, one)
    

 

DP 코드

 

tc = int(input())
for _ in range(tc):
    n = int(input())
    fibs = [(1, 0), (0, 1)]
    for i in range(2, n+1):
        fibs.append((fibs[i-1][0] + fibs[i-2][0], fibs[i-1][1] + fibs[i-2][1]))
    print(f'{fibs[n][0]} {fibs[n][1]}')