n번째 피보나치 수가 10의 배수인지 확인하는 효율적인 방법

이 글에서는 n번째 피보나치 수가 10의 배수인지 효율적으로 판별하는 방법을 알아봅니다. 피보나치 수열은 다음과 같습니다.

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987}

여기서 15번째(0부터 셀 때) 피보나치 수는 10으로 나누어 떨어집니다. 따라서 n이 15일 경우 참(true)을 반환하면 됩니다.

단순한 접근법의 한계

가장 직관적인 방법은 주어진 항까지 피보나치 수를 모두 계산한 뒤, 해당 값이 10으로 나누어 떨어지는지 확인하는 것입니다. 하지만 이 방법은 항 번호가 커질수록 연산량이 기하급수적으로 늘어나기 때문에 큰 수에는 적합하지 않습니다.

수열의 규칙성을 활용한 효율적인 접근법

피보나치 수열에는 흥미로운 규칙이 숨어 있습니다. 먼저 2의 배수에 주목해 보겠습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

굵게 표시된 수들은 모두 2로 나누어 떨어지며, 정확히 3개 항마다 반복해서 등장합니다.

다음으로 5의 배수를 살펴보겠습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

마찬가지로 매 5번째 항마다 5로 나누어 떨어지는 수가 나타납니다.

여기서 2와 5의 최소공배수(LCM)는 15입니다. 즉, n이 15의 배수일 때, 그리고 그때만 n번째 피보나치 수가 10으로 나누어 떨어집니다.

알고리즘

fiboDivTen(term)

시작
    만약 term이 15로 나누어 떨어지면
        true 반환
    종료
    false 반환
끝

예제 코드

#include<iostream>
using namespace std;
bool fiboDivTen(int term) {
    if(term % 15 == 0){
        return true;
    }
    return false;
}
int main() {
    int term = 45;
    if (fiboDivTen(term))
        cout << "Divisible";
    else
        cout << "Not Divisible";
}

실행 결과

Divisible

위 예제에서 45는 15의 배수이므로 45번째 피보나치 수는 10으로 나누어 떨어집니다. 이처럼 복잡한 피보나치 수 계산 없이 단순한 나머지 연산 하나만으로 문제를 상수 시간 O(1) 안에 해결할 수 있습니다.