(Python) - 백준(BOJ) 10826 : 피보나치 수 4

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

10826번: 피보나치 수 4

대표 dp문제였습니다.

📕 풀이방법

📔 입력 및 초기화

항 n, fibonacci수열을 저장할 일차원 배열 fibo을 선언 후 n에 입력받습니다.

📔 풀이과정

점화식은 f[n] = f[n-1] + f[n-2] (n >= 2, f[0] = 0, f[1] = 1) 입니다. 두 가지 풀이가 있습니다.

1. for loop를 2이상 ~ n이하까지 수행해 각 항의 수열값을 구해 fibo에 append해줍니다.

2. 재귀와 memoization을 이용해 이전 값을 사용해 다음 항을 구해줍니다.

📔 정답출력

fibo[n]을 출력합니다.

---

📕 Code

for loop

import sys
input = sys.stdin.readline

n = int(input())
fibo = [0,1]

for i in range(2, n+1):
    fibo.append(fibo[i-1] + fibo[i-2])
    
print(fibo[n])

 

recursion + memoization

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
f = [0 for i in range(10001)]

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