[백준][21단계 동적 계획법 1] 24416번 /알고리즘 수업 - 피보나치 수 1 (파이썬/Python)

1. 문제 설명

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

 

2. 코드

import sys
input = sys.stdin.readline

n = int(input().strip())

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

cnt1 = f[n]
cnt2 = n - 2
print(cnt1, cnt2)

3. 풀이 과정

cnt1은 재귀 fib의 실행 횟수이고, cnt2는 동적 프로그래밍(DP)의 실행 횟수이다.

DP는 배열 f에 저장된 값을 꺼내어 쓰기 때문에 n이 1,2일 때를 제외한 n-2번으로 고정된다.

재귀 횟수는 fib 값 자체이기 때문에 f[n]으로 고정된다.

4. 자투리 개념

• 동적 프로그래밍(Dynamic Programming)
  - 이미 계산한 값을 버리지 않고 배열에 저장하여 필요한 순간 바로 꺼내 쓰는 방식
  - '작은 문제의 해답을 저장해두고, 그것을 이용해 큰 문제를 해결한다.'