[python/백준] 2748. 피보나치 수2(B1)

📌 문제 탐색하기

👉 문제바로가기

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열입니다.

주어진 문제에서 피보나치 수열은 0, 1로 시작하기 때문에 해당 숫자는 고정적입니다. 이후 F(n) = F(n-1) + F(n-2) (n ≥ 2)을 따릅니다.

📌 알고리즘 선택

다이나믹 프로그래밍으로 풀 수 있을지 어떻게 알 수 있을까요?
다음 조건을 만족하는 경우 우리는 다이나믹 프로그래밍을 사용할 수 있습니다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 이러한 조건을 만족하는 대표 문제입니다.

다이나믹 프로그래밍(Dynamic Programming)

• 탑다운 방식
• 보텀업 방식

재귀함수를 사용하는 탑다운 방식 대신에 반복문을 사용하는 보텀업 방식을 사용하면 오버헤드를 줄일 수 있습니다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍의 성능이 더 좋기 때문에 이 문제에서도 보텀업 방식을 이용하여 문제를 해결해보겠습니다.

DP 설계하기

DP문제를 풀기 위해서는 아래 3가지 단계가 필요합니다.
1. 관계식 만들기
2. 가장 작은 문제의 답 구해놓기
3. 값 기록해 나가기

1. 관계식 만들기

n번째 피보나치 수열은 n-1번째 피보나치 수열 + n-2번째 피보나치 수열입니다.

dp[n] = dp[n-1] + dp[n-2]

2. 가장 작은 문제의 답 구해놓기

DP는 앞에서 계산해놓은 값을 활용해 뒤의 문제의 답을 구하는 방식입니다. 따라서 최초 두 개의 값은 미리 알고있어야 뒤의 문제를 해결할 수 있습니다. 이 문제에서는 0번째 피보나치 수와 1번째 피보나치 수를 미리 기록해두면 됩니다.

dp[0] = 0
dp[1] = 1

3. 값 기록해 나가기

n번째 피보나치 수를 구하기까지 관계식들을 통해 앞의 피보나치 수들을 구해가면서 그 값을 배열에 기록하면됩니다.

시간복잡도

다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)입니다. 최대 N은 90개이기 때문에 1초의 시간 안에 연산이 가능합니다.

📌 코드 설계하기

1. n을 Input 받습니다.
2. 앞서 계산된 결과를 저장하기 위한 dp테이블을 초기화합니다.
3. 피보나치 함수를 반복문으로 구현합니다.
4. n번째 피보나치 수를 출력합니다.

📌 정답 코드

import sys

n = int(sys.stdin.readline())
dp = [0] * (n+2)

dp[1] = 0
dp[2] = 1

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

print(dp[n+1])