[백준] 1003번 피보나치 수열

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
    int n;
    int dp[41]={0,1,1};
    for(int i=3; i<41; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    cin>>n;
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        if(x==0)
            cout<<1<<' '<<0<<'\n';
        else if (x==1)
            cout<< 0 <<' '<<1<<'\n';
        else
        cout<< dp[x-1] << ' ' << dp[x]<<'\n';
    }
}

<풀이>

0과 1의 개수가 피보나치 수열을 이룬다.

1의 개수는 0일때 0, 1일때 1, 2일때 1, 3일때 2 ...

0의 개수는 0일때 1, 1일때 0, 2일때 1, 3일때 1, 4일때  2 ...