[python] 백준 2747번 피보나치 수

백준 2747번 피보나치 수

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

문제

풀이

피보나치는 크게 3가지 방법으로 풀 수 있다.

1. 재귀
   가장 흔히 알려진 방법이다.

def recursive(i):
    if i == 1 or i == 2:
        return 1
    else: 
        return recursive(i-1) + recursive(i-2)

a = recursive(10)
print(a)

1 1 2 3 5 8 13 21 34 55 89
an = a(n-1) + a (n-2)의 점화식을 갖는다.

하지만 이렇게 되면 똑같은 수를 여러 번 계산하게 되어 효율성이 떨어진다.
그렇다면 이미 계산한 수를 저장하면 된다!

2. 탑다운 방식

d = [0] * 101  # 피보나치 수열 값을 저장하는 배열, 인덱스를 맞추기 위해 101로 설정

def fibo(x):
    if x == 1 or x == 2:
        return 1
    
    if d[x] != 0:
        return d[x]

    d[x] = fibo(x-1) + fibo(x-2)  # 메모이제이션을 통해 값을 저장
    return d[x]

print(fibo(10))  # fibo(10)의 결과를 출력

3. 다이나믹 프로그래밍 방식 (보텀업)

n = int(input())

data = [0] * 46

data[1] = 1
data[2] = 1

for i in range(3, n+1):
    data[i] = data[i-1] + data[i-2]


print(data[n])

📌 주의

점화식을 생각하는 것이 DP의 핵심 방법 같다.