[BOJ / C++] 피보나치 함수 (다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/1003

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;

    vector<vector<int>> d(41, vector<int>(2, 0));
    d[0][0] = 1;
    d[0][1] = 0;
    d[1][0] = 0;
    d[1][1] = 1;
    for (int i = 2; i <= 40; i++) {
        d[i][0] = d[i-2][0] + d[i-1][0];
        d[i][1] = d[i-2][1] + d[i-1][1];
    }

    while (t--) {
        int n;
        cin >> n;
        cout << d[n][0] << ' ' << d[n][1] << '\n';
    }
}

 

 

2. 분석

문제대로 구현하면 재귀 호출이 일어나기 때문에 시간복잡도가 O(2^n)이 되어 시간초과 판정이 난다. 이 문제는 다이나믹프로그래밍을 이용해서 구현해야한다. 

 

1. dp 테이블:

d[i][0]: n==i에서 0을 호출하는 횟수

d[i][1]: n==i에서 1을 호출하는 횟수

 

2. 점화식

d[i][0] = d[i-2][0] + d[i-1][0];

d[i][1] = d[i-2][1] + d[i-2][1];

 

재귀 호출식을 그림으로 그려보면 점화식 이해가 쉽다. d[i] = d[i-1] + d[i-2]이므로 0과 1 호출 횟수도 동일하게 된다.

 

 

3. 시간복잡도

dp테이블을 채우는데 시간이 걸리는것이 전부이므로 40개만 처리하면 된다. 따라서 시간제한 0.25초 내에 통과 가능하다.