[백준-2748(DP)]피보나치 수 2

문제바로가기

 

문제

피보나치 수는 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번째 피보나치 수를 출력한다.

 

예제 입력

10

예제 출력 

55

 

---

문제 요약

• 피보나치 수:
  F(0)=0F(0) = 0F(0)=0, F(1)=1F(1) = 1F(1)=1, F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)
• 입력: 1 ≤ n ≤ 90
• 출력: n번째 피보나치 수

탑 다운방식

import sys                      # 표준 입력을 더 빠르게 받기 위해 sys 모듈을 가져옵니다.
input = sys.stdin.readline      # input() 대신 readline()을 사용하여 입력 속도를 높입니다.

n = int(input())                # 사용자로부터 정수 n을 입력받습니다.

def fib(n):                     
    # DP 배열 생성 해둔다.
    dp = [0] * (n + 1)          # 크기 n+1의 리스트를 0으로 초기화하여 동적 계획용 배열 생성

    dp[0], dp[1] = 0, 1         # 피보나치 초기값 설정: F(0) = 0, F(1) = 1

    # n이 0 또는 1일 경우 예외처리
    if n == 0:                  
        return 0                # n이 0이면 0 반환
    elif n == 1:                
        return 1                # n이 1이면 1 반환

    # 점화식을 이용하여 반복적으로 계산
    for i in range(2, n + 1):   # 2부터 n까지 반복하면서
        dp[i] = dp[i - 1] + dp[i - 2]  # F(i) = F(i-1) + F(i-2) 를 점화식으로 계산

    return dp[n]                # n번째 피보나치 수를 반환

print(fib(n))                   # 계산된 결과를 출력

바텀업 방식

import sys                       # 빠른 입력을 위해 sys 모듈을 가져옴
input = sys.stdin.readline       # 표준 입력을 빠르게 받기 위한 설정

n = int(input())                 # 사용자로부터 정수 n 입력 받기

def fib(n):
    # n번째 피보나치 수를 저장할 DP(동적 프로그래밍) 배열 생성
    dp = [0] * (n + 1)           # 크기 n+1의 리스트 생성, 모든 값은 0으로 초기화

    dp[0], dp[1] = 0, 1          # 초기값 설정: F(0) = 0, F(1) = 1

    # n이 0일 경우 바로 0을 반환
    if n == 0:
        return 0
    # n이 1일 경우 바로 1을 반환
    elif n == 1:
        return 1

    # 점화식을 이용해 2부터 n까지의 피보나치 수를 차례로 계산
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # F(i) = F(i-1) + F(i-2)

    return dp[n]                # 계산된 n번째 피보나치 수를 반환

print(fib(n))                   # 결과 출력