[1day 1sol] 피보나치 수 5

문제

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

10870번: 피보나치 수 5

 

구현

• Fn = Fn-1 + Fn-2 (n ≥ 2)
• 피보나치 함수 구현
• 함수를 구현하는데 메모리 최적화와 시간을 줄이기 위해서 dictionary를 이용해서 연산과정의 시간을 줄일 수 있었다.
• 물론 n이 20이하의 자연수라 시간초과는 딕셔너리를 사용하지 않아도된다.
• 하지만 추후 메모리 문제와 시간초과를 관리해주는 것이 좋다.

 

코드

import sys

input = sys.stdin.readline

# Fn = Fn-1 + Fn-2 (n >= 2)


def fib(n, memo):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        if n not in memo:
            memo[n] = fib(n-1, memo) + fib(n-2, memo)
            return memo[n]
        else:
            return memo[n]


num = int(input())
dictionary = dict()
print(fib(num, dictionary))

 

느낀점

재귀 함수를 구현하여 반복적인 코드를 줄임으로써, 코드의 양을 줄일 수 있었다. 또한 딕셔너리를 활용하여 시간초과와 메모리 문제를 일으킬 경우의 수까지 생각할 수 있는 문제였다. 단순한 구현이 아닌 최적화에도 신경쓸 수 있는 개발자가 되어야겠다.