백준 1003 : 피보나치 함수

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

1. 접근

• 당연히, 기존에 있는 DFS식, 재귀함수식 함수를 그대로 사용하면 시간초과가 난다.
• n번째 값은 n-1과 n-2의 값을 더해서 이루어지고, 이는 0의 호출과 1의 호출에서도 동일하게 적용된다.
  => DP로 접근하여 n까지의 값을 미리 구하고 그 결괏값을 출력하는 것이 더 빠르다.

2. 나의 풀이

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

vector<pair<int, int>> dp;
void fibonacci(int n) {
    for (int i = dp.size(); i <= n; i++) {
        dp.push_back(make_pair(dp[i - 1].first + dp[i - 2].first, dp[i - 1].second + dp[i - 2].second));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    dp.push_back(make_pair(1, 0));
    dp.push_back(make_pair(0, 1));

    int t, n;
    cin >> t;
    while (t-- > 0) {
        cin >> n;
        fibonacci(n);
        cout << dp[n].first <<" "<<dp[n].second<<"\n";
    }

	return 0;
}