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

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

문제 접근

피보나치 수열이다. 재귀함수 말고 동적 프로그래밍으로 풀면 어떤게 좋은지 알아보기 위한 문이다.

동적 프로그래밍(DP)이란?

동적 프로그래밍(Dynamic Programming)은
복잡한 문제를 작은 하위 문제들로 나누고,
그 결과를 저장(Memoization)해
중복 계산을 피하면서 문제를 해결하는 알고리즘 설계 기법이다.

언제 쓰면 좋을까?

문제를 작은 문제로 나눌 수 있을 때
같은 계산이 여러 번 반복될 때

해답 및 풀이

n = int(input())

# fib(1) 또는 fib(2)가 호출되는 횟수는 n번째 피보나치 수와 같다
def fib_count(n):
    dp = [0] * (n+1)
    dp[1] = dp[2] = 1
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 반복문이 몇 번 실행되는지는 이 구현에서 for문 반복 횟수로 측정 (n-2번)
def fibonacci_count(n):
    return n - 2  # i = 3부터 n까지 돌기 때문

print(fib_count(n), fibonacci_count(n))