문제 개요
주어진 인덱스에 해당하는 N개의 피보나치 수에 대한 최대공약수(GCD)를 구하는 것이 이번 글의 목표입니다. 먼저 입력된 인덱스 중 최댓값을 확인하여 피보나치 수열을 생성해야 합니다. 피보나치 수열은 다음과 같은 형태를 가집니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
인덱스는 0부터 시작하므로 0번째 인덱스의 값은 0입니다. 예를 들어 인덱스 {2, 3, 4, 5}에 해당하는 피보나치 수는 각각 {1, 2, 3, 5}이며, 이 수들의 GCD는 1입니다.
핵심 원리: 피보나치 수의 GCD 성질
이 문제는 하나의 흥미로운 수학적 성질을 활용하면 매우 효율적으로 해결할 수 있습니다. i번째 피보나치 수와 j번째 피보나치 수의 최대공약수는 다음과 같은 관계를 만족합니다.
GCD(Fibo(i), Fibo(j)) = Fibo(GCD(i, j))
즉, 두 피보나치 수의 GCD는 '인덱스들의 GCD'에 해당하는 피보나치 수와 같습니다. 이 성질은 세 개 이상의 피보나치 수에 대해서도 동일하게 적용됩니다. 따라서 복잡한 연산 없이 다음 순서로 문제를 해결할 수 있습니다.
- 주어진 모든 인덱스의 GCD를 구합니다.
- 그 GCD 값을 인덱스로 하는 피보나치 수를 계산합니다.
- 계산된 피보나치 수가 곧 정답이 됩니다.
C++ 구현 예제
#include <iostream>
#include <algorithm>
using namespace std;
int getFiboTerm(int n){
int fibo[n + 2];
fibo[0] = 0; fibo[1] = 1;
for(int i = 2; i <= n; i++){
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
return fibo[n];
}
int getNFiboGCD(int arr[], int n){
int gcd = 0;
for(int i = 0; i < n; i++){
gcd = __gcd(gcd, arr[i]);
}
return getFiboTerm(gcd);
}
int main() {
int indices[] = {3, 6, 9};
int n = sizeof(indices)/sizeof(indices[0]);
cout << "GCD of fibo terms using indices: " <<
getNFiboGCD(indices, n);
}
실행 결과
GCD of fibo terms using indices: 2
코드 동작 설명
getFiboTerm() 함수는 동적 프로그래밍(DP) 기법으로 n번째 피보나치 수를 계산합니다. 반복문을 통해 이전 두 항의 합을 차례대로 저장하므로 시간 복잡도는 O(n)입니다.
getNFiboGCD() 함수는 배열에 담긴 모든 인덱스에 대해 __gcd() 함수를 누적적으로 적용하여 전체 GCD를 구한 뒤, 그 값에 해당하는 피보나치 수를 반환합니다.
예제에서 사용된 인덱스는 {3, 6, 9}입니다. GCD(3, 6, 9) = 3이고, 3번째 피보나치 수는 2이므로 최종 결과로 2가 출력됩니다.