[파이썬/Python] 백준 2748번: 피보나치 수 2

📌 문제 : 백준 2748번

---

📌 문제 탐색하기

n : 구해야 할 피보나치 수의 순서 (1 ≤ n ≤ 90)

✅ 입력 조건
1. n 입력
✅ 출력 조건
1. n번째 피보나치 수 출력

피보나치 수의 점화식은 다음과 같다.
$F_n = F_{n-1} + F_{n-2}$
피보나치 수의 초기 값은 $F_1 = 1, F_2 = 2$이다.

for문을 통해 입력에 따라 피보나치 수를 구하거나 재귀 함수를 이용하여 피보나치 수를 계산할 수 있지만,
동적계획법을 활용하면 중복 연산을 줄여 더 효율적이다.

피보나치 수의 점화식을 이용해 3부터 n까지의 범위 내 모든 피보나치 수를 for문으로 계산하고,
DP 테이블에 저장한다.
DP 테이블의 인덱스 n에 접근해 값을 구해주면 원하는 n번째 피보나치 수를 바로 출력할 수 있다.

가능한 시간복잡도

dp 테이블 생성 → $O(n)$
피보나치 수 계산→ $O(n)$

최종 시간복잡도
$O(n)$으로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

for문으로 범위 내 모든 피보나치 수를 계산하여 DP 테이블에 저장하기

---

📌 코드 설계하기

1. n 입력
2. dp 테이블 정의 및 초기화
3. 피보나치 수 계산해 dp 테이블 채우기
4. 원하는 형식으로 출력
   
   

---

📌 시도 회차 수정 사항

1회차

# 2. dp 테이블 정의 및 초기화
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 1

• 결과
  
• dp 테이블 초기화를 위해 위와 같이 정의했는데 n=1인 경우엔 dp[2]가 존재하지 않아서 IndexError가 발생했다.

# 2-1. n 값에 따라 dp 테이블 초기화
dp[1] = 1

if n > 1:
    dp[2] = 1

• 이와 같이 n=1일 때 예외처리를 해주어 해결했다.
  
  

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. n 입력
n = int(input())

# 2. dp 테이블 정의
dp = [0] * (n+1)

# 2-1. n 값에 따라 dp 테이블 초기화
dp[1] = 1

if n > 1:
    dp[2] = 1

# 3. 피보나치 수 계산해 dp 테이블 채우기
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

# 4. 원하는 형식으로 출력
print(dp[n])

• 결과
  

다른 풀이

n = int(input())
dp = []
dp.append(0)
dp.append(1)

for i in range(2,n+1):
    dp.append(dp[i-1]+dp[i-2])
    
print(dp[n])

• 결과
  
• 유사하지만 dp 테이블 값을 변경하는 것이 아니라 계산해 append하는 방식이다.
  
  

---

📌 회고

• dp 테이블을 초기화할 때 초기값 설정에서 고려할 점이 없는지 다시 한번 살펴야겠다.