[python] 10870. 피보나치 수 5

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

 

 

풀이 

 

이번 문제는 피보나치를 구하는 문제입니다. 

피보나치는 f(n) = f(n-1) + f(n-2)의 점화식으로 구할 수 있는 쉬운 문제입니다.

 

문제는 크게 두 가지의 방법으로 해결할 수 있습니다.

1. 재귀 

2. for loop

 

저는 재귀 중 memoization 방법으로 ! 

한 번 계산한 fibo(n)는 arr에 저장하고, 다시 계산하지 않는 방법으로 풀었습니다. 

 

세 가지 방법은 아래의 코드처럼 풀이할 수 있습니다.

 

 

 

- 기본 코드 (재귀)

def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)	# 앞 두 수의 합

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

 

 

 

- 기본 코드 (for loop)

n = int(input())

fibonacci = [0, 1]
for i in range(2, n+1):
    num = fibonacci[i-1] + fibonacci[i-2]
    fibonacci.append(num)
print(fibonacci[n])

 

 

 

- 나의 코드 

arr = [-1]*21

arr[0] = 0
arr[1] = 1
def fibo(n):
    if arr[n] != -1:
        return arr[n]
    if n >= 2:
        arr[n] = fibo(n-1) + fibo(n-2)

    return arr[n]

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