[백준] 4150번 피보나치 수 - 파이썬

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

4150번: 피보나치 수

풀이 1

피보나치 수를 점화식을 사용해서 문제를 풀어준다.

# 4150번 피보나치 수
n = int(input())
# dp 생성
fibo = [0, 1]
for i in range(2, n+1):
    fibo.append(fibo[i-1] + fibo[i-2])
print(fibo[n])

출력결과

 

풀이 2(시간초과)

재귀함수 사용하게되며 시간초과 일어난다.

# 4150번 재귀함수 사용
import sys
sys.setrecursionlimit(10 ** 6)
def fibo(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return fibo(n-1) + fibo(n-2)

n = int(input())
print(fibo(n))