2748) 피보나치 수 2

📌 문제 탐색하기

• 피보나치 수는 0과 1로 시작
• Fn = Fn-1 + Fn-2
• 즉, n = 10이면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
• N번째 피보나치 수를 구하기

가능한 시간복잡도

N번째 피보나치 수를 구할 때 까지 N번의 연산이 필요.
따라서 O(N)이 되고, N은 최대 90개 이기 때문에 1초의 시간안에 연산 가능.

알고리즘 선택

DP : 앞에 계산해 놓은 값을 재활용해 뒤의 문제의 답을 구하는 방식

📌 풀이하기

• DP 관계식 구하기
  dp[N] = dp[n-1] + dp[n-2]

📌 코드 설계하기

1. 문제의 input을 받는다.
2. 가장 작은 문제의 답(피보나치 0,1번째 수)를 먼저 구한다.
3. DP 관계식을 구현하고, N번 째 수까지의 답을 순차적으로 탐색한다.

📌 시도 회차 수정 사항 (Optional)

📌 정답 코드

# 백준 2578
import sys

n = int(sys.stdin.readline())

dp = []
dp.append(0)
dp.append(1)

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

print(dp[n])