백준 (boj) 파이썬 - 2748 피보나치 수 2

문제 링크 : https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

 

 

피보나치 수를, 재귀함수가 아닌 다른방법 (반복문)으로 구현하라는 문제였다. 숫자 범위가 꽤 컸는데, 실제로 해보니 시간초과가 발생했다.

재귀함수로 구현하게되면 연속적으로 함수를 호출하게 되면서 stack overflow를 유발한다고 한다. (return 하기 전에는 계속하여 메모리에 축적되기 때문에)

 

 

*파이썬 코드

n = int(input())

arr = [0,1,1]
if n < 3 : answer = arr[n] 
else:
    while(True):
        arr.append(sum(arr[-2:]))

        if len(arr)>n : 
            answer = arr[n]
            break

print(answer)