[백준] 2748번 피보나치 수 2 파이썬 정답 코드

2748번: 피보나치 수 2

---

1. 문제 내용

 

 

2. 접근 방식

• 다이나믹 프로그래밍(DP)

피보나치를 구하는 가장 일반적인 재귀 함수 방식은 시간 복잡도가 O(2^n)이다. 이 문제에서 n은 90보다 작거나 같은 자연수이므로, 재귀 함수 방식으론 절대 풀 수가 없다. 따라서 작은 문제에서 큰 문제로 차근차근 답을 도출하는 다이나믹 프로그래밍의 상향식 방식을 따라 dp 테이블을 사용하여 피보나치 수를 구한다.

 

 

3. 정답 코드

n = int(input())

dp = [0] * 91
dp[0], dp[1] = 0, 1

for i in range(2, n + 1):
    if not dp[i]:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n])