BOJ 1003 ) 피보나치 함수

 

1003번: 피보나치 함수

간단한 DP로 해결할 수 있는 문제다. '피보나치 + 제한시간이 짧음' 에서 바로 DP가 생각나서 그렇게 풀었다. 그냥 피보나치문제를 풀 수 있다면 어려움 없이 풀 수 있는 문제.

#include <iostream>
#include <vector>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int T,N;
pii fib[42];

void makefib(){
    fib[0]={1,0};
    fib[1]={0,1};
    for(int i=2;i<=40;i++){
        fib[i].x=fib[i-1].x+fib[i-2].x;
        fib[i].y=fib[i-1].y+fib[i-2].y;
    }
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>T;
    makefib();
    while(T--){
        cin>>N;
        cout<<fib[N].x<<" "<<fib[N].y<<'\n' ;
    }
}