C++에서 N번째 짝수 피보나치 수 찾기: 재귀 공식을 활용한 효율적인 풀이

이 문제에서는 정수 값 N이 주어지며, 우리의 과제는 N번째 짝수 피보나치 수(Even Fibonacci Number)를 찾는 것입니다.

피보나치 수열은 이전 두 수를 더하여 다음 수를 생성하는 수열입니다. 피보나치 수열은 두 개의 초기값 F0과 F1에서 시작하며, 초기값은 각각 0, 1 또는 1, 1로 설정할 수 있습니다.

예시를 통해 문제를 이해해 보겠습니다.

입력 : N = 4
출력 : 144

해결 접근 방식

이 문제의 핵심 아이디어는 피보나치 수열에서 매 세 번째 수가 짝수라는 사실을 활용하는 것입니다. 그리고 짝수 피보나치 수들 역시 하나의 재귀 공식을 따른다는 점을 이용하면 됩니다.

짝수 피보나치 수열의 재귀 공식은 다음과 같습니다.

Ef(n) = 4·Ef(n-1) + Ef(n-2)  (단, Ef(0) = 0, Ef(1) = 2)

피보나치 수열에서 세 번째마다 짝수가 등장하므로, f(n-3)과 f(n-6)도 모두 짝수가 됩니다. 따라서 f(n)을 짝수 피보나치 수열의 k번째 원소인 Ef(k)라고 하면, f(n-3)은 바로 앞의 짝수인 Ef(k-1)에 해당하고, f(n-6)은 그 앞의 짝수인 Ef(k-2)에 해당합니다.

이로써 다음 관계식이 성립합니다.

f(n) = 4·f(n-3) + f(n-6)
즉, Ef(k) = 4·Ef(k-1) + Ef(k-2)

이 공식을 사용하면 전체 피보나치 수열을 일일이 계산하지 않고도 짝수 피보나치 수만을 대상으로 빠르게 원하는 값을 구할 수 있습니다.

예제 코드

아래는 위에서 설명한 솔루션의 동작을 보여주는 C++ 프로그램입니다.

#include<iostream>
using namespace std;

int findNthEvenFiboNum(int n){
    if (n < 1)
        return n;
    if (n == 1)
        return 2;
    return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n-2));
}

int main (){
    int n = 5;
    cout<<n<<"th even fibonacci number is "<<findNthEvenFiboNum(n);
    return 0;
}

실행 결과

5th even fibonacci number is 610