BOJ 1003 피보나치 함수

피보나치 함수 [실버3]

---

문제 링크

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

풀이

N이 0,1에 대해 초기설정을 해준 뒤, 규칙성을 찾아 미리 구한 값들을 출력하면 된다.

#include <iostream>
using namespace std;

int T, N;
int dp[41][2];

int main(void)
{
    cin >> T;

    dp[0][0] = 1;
    dp[0][1] = 0;

    dp[1][0] = 0;
    dp[1][1] = 1;

    /*
    2 => 1 0
    3 => 2(1 0) 1(1)
    4 => 3(1 1 0) 2(1 0)
    5 => 4(1 1 0 1 0) 3(1 1 0)
    */
    for (int i = 2; i <= 40; ++i)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
        dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
    }


    for (int t = 0; t < T; t++)
    {
        cin >> N;
        cout << dp[N][0] << " " << dp[N][1] << "\n";
    }
}