[다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2

[백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2

(한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제!

2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다.

2747번은 n의 범위가 45이하 자연수이고 2748번은 n의 범위가 90이하 자연수이다.

일단 두 문제 모두 일반 재귀로 피보나치 수를 구하려면 시간복잡도가 (2**n)으로 45이면 2**45(약 10**12), 90이면 2**90(약 10**27)으로 시간 초과가 나올 것이다. 그러므로 dp로 풀어야한다!

(풀이1) 반복문 이용

풀이 시간: 5분 이내

1) 문제 해결 아이디어

 

2) 소스코드

n = int(input())  # 1. 45이하 자연수, 2. 90이하 자연수
d = [0] * (n + 1)
d[0], d[1] = 0, 1
for i in range(2, n + 1) :
  d[i] = (d[i - 1] + d[i - 2])
print(d[n])

(풀이2) 재귀 이용

풀이 시간: 5분 이내

1) 문제 해결 아이디어

 

2) 소스코드

def fibo(x):
  if x == 0:  return 0
  if x == 1:  return 1
  # 기록되지 않았으면 계산
  if d[x] == 0:  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]

n = int(input())  # 90이하 자연수
d = [0] * (n + 1)
d[0], d[1] = 0, 1
fibo(n)
print(d[n])  # n번째 피보나치수