[파이썬, Python] 백준 24416: 피보나치 수 1

문제

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

24416번: 알고리즘 수업 - 피보나치 수 1

코드

import sys
input = sys.stdin.readline

n = int(input())

cnt_2 = 0

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

li = [1 for i in range(41)]

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

print(fib(n), cnt_2)

설명

피보나치 수를 재귀 형식과 동적 프로그래밍(다이나믹 프로그래밍) 방식으로 구했을 때의 차이점을 알아보는 문제이다.

재귀 형식 같은 경우는 문제에 나와있는 코드를 그대로 구현해서 피보나치 수를 출력해주면 된다.

다이나믹 프로그래밍의 경우는 우선 리스트를 생성해준다.
1로 이루어진 41개의 리스트를 생성했는데,
0번째를 1번째로 보지 않고, 1번째를 1번째로 보기 위함이다.

이후 2부터 n까지의 반복문을 통해 리스트의 i번째 값을 i-1번째와 i-2번째의 값을 더해준 값으로 지정해주면
피보나치 수를 다이나믹 프로그래밍으로 구현이 가능하다.
함수가 1번 실행될 때 마다 카운트해주고 이를 출력한다.