[프로그래머스] 피보나치 수 python(level 2)

https://school.programmers.co.kr/learn/courses/30/lessons/12945?language=python3

1트

메모이제이션, dynamic programming
이전에 했던 작업을 또 하는 경우 시간초과가 날 수 있다. 공간복잡도를 생각해서 저장해놓도록하자.

내 풀이

# 피보나치 수 구현
# 2이상의 n이 입력
# n번째 피보나치 수를 1234567로 나눈 나머지를 리턴


import sys

FIBONACCI = dict()
FIBONACCI[0] = 0
FIBONACCI[1] = 1
FIBONACCI[2] = 1
FIBONACCI[3] = 2


def get_fibonacci(n):
    if n in FIBONACCI.keys():
        return FIBONACCI[n]
    else:
        FIBONACCI[n] = get_fibonacci(n - 1) + get_fibonacci(n - 2)
        return FIBONACCI[n]


def solution(n):
    sys.setrecursionlimit(10 ** 6)
    answer = get_fibonacci(n)

    return answer % 1234567