백준 1003번 C++ 풀이

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

1003번: 피보나치 함수

 

 

시간제한이 0.25초이므로 일반적인 재귀나 반복으로 접근하면 틀리는 문제. dp로 접근해야한다.

 

n번째의 피보나치 수열을 fib(n)이라고 하자. 그렇다면 fib(0)의 경우는 0을 한번 호출하므로 1 0이 될 것이다. fib(1)은 1을 한번 호출하므로 0 1이 될 것이다. 이 둘을 기본 틀로 잡자.

 

fib(2)는 1과 0을 호출하므로 1 1이 되고, 이것은 fib(1)과 fib(0)이 호출한 횟수의 총합과 같다.

fib(3)은 fib(2)와 fib(1)을 호출하고 fib(2)는 다시 fib(1)과 fib(0)을 호출하여 1 2가 될 것이다. 

 

즉, fib(n)은 fib(n-1)과 fib(n-2)가 각각 0과 1을 호출한 횟수의 합과 같아진다.

 

또한 n의 범위가 크지 않으므로, 처음부터 이를 계산해놓고 시작하면 시간제한 안에 통과할 수 있다.

 

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test, n; // test case, input
    vector<pair<int, int>> v(41);
    
    v[0] = make_pair(1, 0); // init vector
    v[1] = make_pair(0, 1);
    for (int i = 2; i < 41; ++i)
        v[i] = make_pair(v[i-2].first + v[i-1].first, v[i-2].second + v[i-1].second);
    
    cin >> test;
    while (test--) {
        cin >> n;
        cout << v[n].first << ' ' << v[n].second << '\n';
    }
}