[DP] 백준 #24416 알고리즘 수업 - 피보나치 수 1 - Python

🗂️ 문제

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

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

 

💡 접근법

1. DP로 풀 수 있는지 먼저 확인한다.
   • 부분 문제가 반복적으로 나타나야 한다.
   • 부분 문제의 최적 결과를 사용하여 전체 문제의 최적 결과를 낼 수 있다.
2. DP 테이블을 초기화한다.
3. 조건에 맞는 점화식을 구한다.

 

😎 내 코드

import sys

def fib_recur(n):
    global recur_cnt
    if n == 1 or n == 2:
        recur_cnt += 1
        return 1
    else:
        return fib_recur(n-1) + fib_recur(n-2)

def fib_dp(n):
    global dp_cnt
    f = [0] * (n+1)
    f[1] = f[2] = 1
    for i in range(3, n+1):
        dp_cnt += 1
        f[i] = f[i-1] + f[i-2]
    return f[n]

N = int(sys.stdin.readline())
recur_cnt = dp_cnt = 0

fib_recur(N)
fib_dp(N)

print(recur_cnt, dp_cnt)

 

✅ 정답 확인