이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 C++를 사용하여 N번째 피보나치 수의 마지막 자릿수를 구하는 프로그램을 작성하는 것입니다.
문제 설명
N번째 피보나치 수의 마지막 자릿수, 즉 최하위 자릿수(LSB)를 구해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
- 입력: N = 120
- 출력: 1
풀이 접근 방식
가장 간단한 방법은 피보나치 수열의 일반항 공식을 사용하여 N번째 항을 직접 계산하는 것입니다. 하지만 N이 매우 큰 수일 경우 이 방법은 연산량과 오버플로우 문제로 인해 실용적이지 않습니다.
이 문제를 해결하기 위해 피보나치 수열의 중요한 성질을 활용할 수 있습니다. 바로 마지막 자릿수가 60개 항을 주기로 반복된다는 점입니다. 이를 피사노 주기(Pisano Period)라고 하며, 마지막 자릿수 기준으로 주기가 60입니다. 예를 들어, 75번째 항의 마지막 자릿수는 135번째 항의 마지막 자릿수와 동일합니다.
즉, 60번째 항까지만 계산하면 가능한 모든 마지막 자릿수 조합을 얻을 수 있습니다. 따라서 N을 60으로 나눈 나머지(N mod 60)를 구한 뒤, 해당 위치의 피보나치 수만 계산하면 됩니다. 이렇게 하면 N이 아무리 커도 최대 60번의 반복 연산만으로 답을 구할 수 있어 매우 효율적입니다.
예제 코드
#include <iostream>
using namespace std;
// N번째 피보나치 수를 계산하는 함수
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;
}
// N번째 피보나치 수의 마지막 자릿수를 반환하는 함수
int findLastDigitNterm(int N) {
N = N % 60; // 60주기 성질 활용
return (fibo(N) % 10);
}
int main() {
int N = 683;
cout << "The last digit of " << N << "th Fibonacci term is " << findLastDigitNterm(N);
return 0;
}
실행 결과
The last digit of 683th Fibonacci term is 1
코드 설명
fibo() 함수는 반복문을 사용하여 N번째 피보나치 수를 계산합니다. findLastDigitNterm() 함수는 먼저 N을 60으로 나눈 나머지로 변환하여 계산 범위를 줄인 후, 해당 피보나치 수를 10으로 나눈 나머지를 통해 마지막 자릿수를 얻습니다.
위 예제에서 N = 683인 경우, 683 mod 60 = 23이므로 사실상 23번째 피보나치 수의 마지막 자릿수만 계산하면 되며, 그 결과값은 1입니다. 이처럼 주기 성질을 활용하면 N이 수백만, 수억처럼 큰 값이라도 빠르게 정답을 구할 수 있습니다.