C++로 구현하는 N번째 피보나치 수의 마지막 두 자리 찾기

이 문제에서는 하나의 수 N이 주어지며, 우리의 과제는 C++를 이용해 N번째 피보나치 수의 마지막 두 자리를 구하는 프로그램을 작성하는 것입니다.

문제 설명

N번째 피보나치 수의 마지막 두 자리, 즉 최하위 두 자리 숫자(LSB 2개)를 구해야 합니다. 예시를 통해 문제를 살펴보겠습니다.

입력: N = 120

출력: 81

해결 접근 방법

가장 간단한 방법은 피보나치 일반항 공식을 사용하여 N번째 항을 직접 계산하는 것입니다. 하지만 N이 매우 커지면 이 방법은 현실적으로 사용하기 어렵습니다.

이러한 한계를 극복하기 위해 피보나치 수열의 중요한 성질을 활용할 수 있습니다. 바로 피보나치 수의 마지막 두 자리는 300개 항마다 반복된다는 점입니다. 즉, 75번째 항의 마지막 두 자리와 975번째 항의 마지막 두 자리는 서로 같습니다(이 주기를 피사노 주기라고 부르기도 합니다).

이 성질을 이용하면 처음 300개 항만 계산하면 모든 경우의 조합을 얻을 수 있으며, 어떤 항을 사용해야 하는지는 N을 300으로 나눈 나머지(mod)를 통해 알아낼 수 있습니다.

예제 코드

#include <iostream>
using namespace std;
long int fibo(int N){
    long int a=0,b=1,c;
    for(int i=2; i<= N;i++) {
        c=a+b; a=b; b=c;
    }
    return c;
}
int findLastTwoDigitNterm(int N) {
    N = N % 300;
    return ( fibo(N)%100);
}
int main() {
    int N = 683;
    cout<<"The last two digits of "<<N<<"th Fibonacci term are "<<findLastTwoDigitNterm(N);
    return 0;
}

실행 결과

The last two digits of 683th Fibonacci term are 97

코드 설명

fibo() 함수는 반복문을 사용해 N번째 피보나치 수를 계산합니다. findLastTwoDigitNterm() 함수는 먼저 N을 300으로 나눈 나머지로 줄인 뒤 해당 항을 구하고, 여기에 100으로 나눈 나머지를 취해 마지막 두 자리만 반환합니다. 이렇게 하면 N이 아무리 크더라도 최대 300번의 반복 연산만으로 빠르게 답을 구할 수 있습니다.