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

https://www.acmicpc.net/problem/2748

📌 문제 탐색하기

목표

• 피보나치 수열 계산해서 n 번째 피보나치 수 구하기

입력값

• n이 주어진다. (1 ≤ n ≤ 90)
  • ex)
  • 10

출력값

• n번째 피보나치 수를 구해서 반환한다.
  • ex)
  • 55

📌 코드 설계하기

해결 아이디어

• 흔히 생각하는 일반 피보나치 수열은 재귀를 쓰기 때문에 시간 복잡도가 굉장히 크다. 따라서 시간 제한이 1초로 제한되어있으니 dp를 사용해서 구현해보자.
• dp를 쓰기 위해서는 배열을 정의해야 한다.
• 한 번 fibo(n)을 구하면 배열에 해당 값을 저장한다. 다시 fibo(n)이 필요하면 다시 재귀를 호출하지 않고 저장된 값을 꺼내 쓰도록 하는 것이다. 이렇게 하면 숫자는 단 한 번만 계산된다.

📌 Trouble Shooting

1차 시도

import sys

def fibo(n):
    if arr[n]>0:
        return arr[n]
    if n < 2:
        return n
    else:
        arr[n] = fibo(n-1) + fibo(n-2)
        return arr[n]
    
arr= [0] * 90
n = int(sys.stdin.readline())
print(fibo(n))

• 나름 DP를 써보겠다고 썼는데 런타임 에러 (IndexError) 가 발생했다.
• 고민해보니 arr[0] * 90을 하면 인덱스는 0~89까지만 유효해서 90이 들어오면 index out of range가 나오게 된다.
• 그러면 상한을 늘려주거나 n을 입력 받고 난 후에 배열을 초기화해주면 해결되겠다.

📌 정답 코드

import sys

def fibo(n):
    if arr[n]>0:
        return arr[n]
    if n < 2:
        return n
    else:
        arr[n] = fibo(n-1) + fibo(n-2)
        return arr[n]
    
n = int(sys.stdin.readline())
arr= [0] * (n+1)

print(fibo(n))

시간 복잡도 계산해보기

• fibo()
  • arr[n]이 있기 때문에 같은 n을 두 번 이상 계산하지 않음.
  • fibo(n)은 fibo(n-1), fibo(n-2) … → fibo(0)까지 딱 한 번씩만 실행된다.
  • 따라서 시간 복잡도는 O(N)이 된다.

최종 시간 복잡도: O(N)