1003 - 피보나치 함수

• 난이도: 실버 3
• 날짜: 2023년 2월 12일
• 상태: Correct
• 추가 검토 여부: No
• 알고리즘 : DP

solution

• 입력값 범위에 따라 fibo(40)까지만 연산하면 된다.
• fibo(N)에서 사용하는 fibo(1)과 fibo(0)의 호출수는 fibo(N-1)의 fibo(1), fibo(0)의 호출수와 fibo(N-2)의 fibo(1), fibo(0)의 호출수와 같다.
• 40개의 경우에 대해 이전 값을 배열에 저장해 두는 방식으로 재귀 없이 직접 참조가 가능하다.

code

#include <iostream>
using namespace std;

int main()
{
    int T;
    cin >> T;
    pair<int, int> ans[41];
    for(int i = 0; i < 41; i++)
    {
        ans[i].first = 0;
        ans[i].second = 0;
    }

    ans[0].first = 1; ans[0].second = 0;
    ans[1].first = 0; ans[1].second = 1;
    for(int i = 2; i < 41; i++)
    {
        ans[i].first = ans[i-2].first + ans[i-1].first;
        ans[i].second = ans[i-2].second + ans[i-1].second;
    }

    int N;
    for(int i = 0; i < T; i++)
    {
        cin >> N;
        cout << ans[N].first << " " << ans[N].second << endl;
    }

    return 0;
}

ref

1003번: 피보나치 함수