[백준][Python] 1003번 피보나치 함수 - 코팩

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

풀이

피보나치 함수를 푸는데 3가지 방법이 있다.

1, 직접 구현

2, 재귀함수 이용

3, 다이나믹 프로그래밍 사용(시간 감축)

위 문제는 시간초과 때문에 3번에 해당하는 문제이다. 다만 피보나치의 함수의 값을 dp에 담아주는 것이 아닌 자연수 N의 피보나치 수를 계산할 때 얼마나 0과 1을 리턴하는지를 담아주는 것이다.

# 1003번 피보나치 함수
def fib(n):
    dp_0 = [1, 0, 1]
    dp_1 = [0, 1, 1]
    
    if n >= 3:
        for i in range(3, n+1):
            dp_0.append(dp_0[i-1] + dp_0[i-2])
            dp_1.append(dp_1[i-1] + dp_1[i-2])
    print(dp_0[n], dp_1[n])

t = int(input())
    
for _ in range(t):
    fib(int(input()))

출력결과