[Silver 3] 1003번 피보나치 함수

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

1003번: 피보나치 함수

 

처음 문제를 해결할 때는 주어진 함수를 그대로 사용하고, map을 사용하여 0일 때와 1일 때 

value를 증가시키는 방식을 사용했다. 하지만 이 방식은 시간 초과 문제로 해결할 수 없었다.

이유를 생각해보니 C++에서 함수 호출은 시간이 오래 걸리는 문제가 있었고

이를 해결하기 위해서는 문제에서 규칙을 찾아야 하는 것을 알게 되었다.

 

문제를 보면 40까지의 수로 한정되어 있으며 이는 반복문으로 40까지의 수를 배열로 초기화하면 된다.

또한 0과 1, 2, 3을 보면 또다른 규칙을 가지고 있다.

0, 1 0
1, 0 1
2, 1 1
3, 1 2
4, 2 3
5, 3 5
6, 5 8
7, 8 13

위와 같은 형식으로 수가 나오게 되며,

1의 경우 0 케이스의 1이 나오는 경우와 0이 나오는 경우를 합한 것이 1이 나오는 경우고

0이 나오는 경우는 0 케이스의 1이 나오는 경우를 가져오면 된다.

즉, N이 나오는 경우는 arr[N - 1]과 arr[N]을 출력하면 되며

arr을 초기화 할때 arr[N] = arr[N - 1] + arr[N - 2]를 하면 된다.

 

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


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin>>T;
    vector<int> arr;
    arr.assign(41, 1);
    arr[0] = 0;
    for(int i = 2;i<=40;i++){
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    for(int i = 0;i<T;i++){
        int N;
        cin>>N;
        if(N == 0) cout<<"1 0"<<'\n';
        else cout<<arr[N-1]<<' '<<arr[N]<<'\n';
    }
}