Baekjoon 1003번 피보나치 함수

문제

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

걸린 시간

00 : 14 : 26

풀이

Python3

dic = {}

def fib(n):
    result = [0, 0]
    if n in dic:
        return dic[n]

    if n == 0:
        result[0] += 1    
        dic[n] = result
        return result
    elif n == 1:
        result[1] += 1
        dic[n] = result
        return result
    else:
        left = fib(n-1)
        right = fib(n-2)
        result[0] = left[0] + right[0]
        result[1] = left[1] + right[1]
        dic[n] = result
        return dic[n] 

if __name__ == "__main__":
    T = int(input())

    result = []

    for _ in range(0, T):
        n = int(input())
        result.append(fib(n))

    for i in result:
        print(i[0], i[1])

피보나치 수열을 순서대로 출력하는 것이 아닌 0과 1의 개수를 기록하는 리스트의 값을 증가시켜 해당 리스트를 반환한다.

딕셔너리(메모이제이션)에 기록되는 값도 마찬가지로 result 리스트이다.