알고리즘 :: 백준 :: DP :: 2747 :: 피보나치수열

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

문제 접근

• DP를 연습하기 위한 기초 문제다.
• 너무나도 익숙한 피보나치 수열을 DP를 이용해서 풀어보자.
• 임의의 수 n은 n-1과 n-2가 피보나치 수열의 어떤 값인지 기록해둔다면 쉽게 구할 수 있으므로 DP를 이용할 수 있다.
• 점화식 $D(n) = D(n-1) + D(n-2) \ \ \ (n>=2)$
• 점화식을 그대로 코드로 옮기면 된다.

코드

#include <iostream>
#include <cstring>
using namespace std;

static int n = 0;
static int cache[45];   // DP용 배열

int fibo(int num) {
    if (num <= 1) return num; // [기저 1] - 더 이상 문제를 분할할 수 없음
    if (cache[num] > 0) return cache[num];  // [기저 2] - 이미 계산된 경우 중복계산 X
    return cache[num] = fibo(num-1) + fibo(num-2);  // 점화식을 이용한 재귀
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    memset(cache, 0, sizeof(cache));
    cout << fibo(n) << '\n';
}

결과