[백준] 2748번 피보나치 수2 Python

📃문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

📃입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

📃출력

첫째 줄에 n번째 피보나치 수를 출력한다.

📃예제 입력 1

10

📃예제 출력 1

55

✏️문제 탐색하기

피보나치 수열의 특정 위치에 있는 값을 구하는 문제입니다. 입력으로 주어지는 n에 따라 n번째 피보나치 수를 계산하여 출력해야 합니다.

주어진 조건:

• 피보나치 수열은 0과 1로 시작합니다.
  F(0) = 0
  F(1) = 1
  그 이후의 피보나치 수는 바로 앞의 두 수의 합으로 정의됩니다.
  F(n) = F(n-1) + F(n-2)

가능한 시간복잡도

반복문을 사용한 접근은 O(n)의 시간 복잡도를 가짐.

✏️알고리즘 선택

동적 프로그래밍을 사용해 이전 계산 결과를 배열에 저장하여 피보나치 수를 계산.

✏️코드 설계하기

1. sys.stdin.readline()을 사용하여 N 값을 입력받습니다.
2. 리스트를 N + 1로 설정하여 dp[i]에 i 번째 피보나치 수를 저장할 수 있도록 합니다.
3. dp[0]은 0, dp[1]은 1로 초기화합니다.
4. 반복문을 통해 dp[2]부터 dp[N]까지의 값을 계산합니다.
5. 피보나치 점화식 F(n) = F(n-1) + F(n-2) 에 따라 dp[i]를 dp[i - 1] + dp[i - 2]로 계산합니다.
6. print(dp[N])를 통해 결과를 출력합니다.

✏️코드 구현

import sys

arr = []
N = int(sys.stdin.readline())
dp = [0] * (N + 1)
dp[1] = 1
for i in range(2, N + 1):
    dp[i] = dp[i-2] + dp[i - 1]
print(dp[N])