배열 A에 N개의 요소가 저장되어 있다고 가정해 보겠습니다. 우리가 구해야 할 값은 배열의 모든 요소에 대해 팩토리얼(계승)을 계산한 뒤, 그 값들의 최대공약수(GCD)입니다. 예를 들어 요소가 {3, 4, 8, 6}이라면 각각의 팩토리얼은 3! = 6, 4! = 24, 6! = 720, 8! = 40320이 되고, 이 넷의 GCD는 6입니다.
핵심 아이디어: 최솟값의 팩토리얼이 곧 정답
두 수의 GCD는 두 수를 모두 나누어 떨어지게 하는 가장 큰 수입니다. 여기에 중요한 수학적 성질이 하나 숨어 있습니다. 바로 n ≤ m일 때 n!은 항상 m!을 나눌 수 있다는 점입니다. 실제로 3! = 6은 5! = 120을 나눌 수 있으며, 그 몫은 5 × 4 = 20이 됩니다.
따라서 두 수 팩토리얼의 GCD는 단순히 더 작은 수의 팩토리얼 자체와 같습니다. 즉, gcd(3!, 5!) = 3! = 6입니다. 이 성질을 세 개 이상의 수로 확장하면 결론은 더욱 간단해집니다. 배열 전체 팩토리얼의 GCD는 배열에서 가장 작은 요소의 팩토리얼과 같습니다.
덕분에 모든 요소의 팩토리얼을 일일이 계산할 필요 없이, 최솟값 하나만 찾아 그 팩토리얼을 구하면 됩니다. 특히 배열의 요소가 클 때 불필요한 연산을 크게 줄여 주는 매우 효율적인 방법입니다.
알고리즘 단계
1. 배열을 한 번 순회하면서 최솟값을 찾습니다.
2. 찾은 최솟값의 팩토리얼을 계산합니다.
3. 계산된 값을 결과로 반환합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
long fact(int n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
int gcd(int arr[], int n) {
int min = arr[0];
for (int i = 1; i < n; i++) {
if(min > arr[i])
min = arr[i];
}
return fact(min);
}
int main() {
int arr[] = {3, 4, 8, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "GCD: "<< gcd(arr, n);
}실행 결과
GCD: 6
코드 설명 및 복잡도
fact() 함수는 재귀 호출을 통해 인자로 받은 수의 팩토리얼을 계산합니다. n이 1 이하일 때 1을 반환하는 것이 재귀의 종료 조건입니다.
gcd() 함수는 배열의 첫 번째 요소를 초기 최솟값으로 설정한 뒤, 나머지 요소들을 순회하며 더 작은 값이 발견되면 갱신합니다. 순회가 끝나면 최솟값의 팩토리얼을 그대로 반환합니다.
시간 복잡도 측면에서 최솟값을 찾는 데 O(N)이 소요되고, 팩토리얼 계산에는 최솟값의 크기에 비례하는 시간이 걸립니다. 모든 요소의 팩토리얼을 직접 구한 뒤 GCD를 계산하는 나이브한 방식보다 훨씬 효율적입니다.
다만 팩토리얼은 값이 급격히 커지는 함수이므로, 요소가 20을 넘어가면 long 타입으로도 오버플로가 발생할 수 있다는 점에 유의해야 합니다. 실제 서비스 환경에서는 임의 정밀도 정수 타입이나 모듈러 연산 등을 함께 고려하는 것이 좋습니다.