[백준] DP 2748번: 피보나치 수 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번째 피보나치 수를 출력한다.

Approach

사용 알고리즘: 다이나믹 프로그래밍

• 단순 재귀함수로 구현하면 시간초과된다. 한번 계산한 값을 DP테이블에 저장해놓음으로써 중복되는 연산을 피해야한다. top-down 방식말고 bottom-up 방식으로 반복문을 이용해 풀었다
• 피보나치 수의 n번째 값은 f(n-1) + f(n-2) 이기 때문에 n-1번째 수와 n-1번째 수의 값을 테이블에 저장해놓고 n번째 수를 계산할 때 그냥 테이블에서 두 수를 꺼내서 쓰면 상수시간으로 풀 수 있다
• 결과적으로 원래는 O(2^n) 의 시간복잡도지만 DP를 쓰면 O(n) 으로 풀 수 있다

Source Code

# include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    long long int d[100] = {0,}; // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
    
    // 첫번째와 두번째 피보나치 수는 무조건 1
    d[1] = 1;
    d[2] = 1;
    
    // bottom-up dynamic programming
    for (int i = 3; i <= n; i++)
    {
        d[i] = d[i - 1] + d[i - 2]; // 이때 d[i-1]과 d[i-2]의 값은 다시 연산할 필요없이 dp테이블에서 값을 꺼내쓰면 된다 
    }
    
    cout << d[n] << endl; // 답안 출력 
    
    return 0;
}