[백준 BOJ_1003] 피보나치 함수 Python 풀이

출처: 백준 온라인 저지

문제

풀이

N에 따라 fib(0)과 fib(1)이 몇 번 호출되는 지 알아보기 위해 0부터 9까지의 결과를 아래에 정리해보았습니다.

N	fib(0)	fib(1)
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21
9	21	34

표를 보면 fib(0)은 N-1번째의 피보나치 수만큼, fib(1)은 N번째의 피보나치 수만큼 호출된다는 것을 확인할 수 있었기 때문에, 결국엔 피보나치 수열을 구하는 문제와 다를 바 없습니다.

피보나치 수열을 구하는 문제는 여러번 풀어봤지만 이번에는 동적계획법을 이용하여 풀어보겠습니다.

일단 값을 저장해줄 cache의 크기는 N의 범위가 0을 포함한 40까지의 수이기 때문에 42만큼 -1로 초기화 해준 뒤, cache[0]과 cache[1]는 각각 0과 1로 초기화 해줍니다.

cache[N]의 값이 -1일 때, 다른 말로 하면 cache[N]의 값을 지정해준적이 없을 때는 재귀호출로 fib(n-1)과 fib(n-2)를 더한 값을 넣어줍니다.

마지막으로 fib(N-1)과 fib(N)을 출력해주면 됩니다.

코드

def fib(n):
    if cache[n] == -1:
        cache[n] = fib(n-1) + fib(n-2)
    return cache[n]
T = int(input())
for _ in range(T):
    cache = [-1] * 42
    cache[0] = 0
    cache[1] = 1
    N = int(input())
    if N == 0:
        print(1, 0)
    else:
        print(fib(N-1), fib(N))