정수 하나가 주어졌을 때, 먼저 그 수의 팩토리얼(계승)을 계산한 다음, 결과값이 몇 자리 숫자로 이루어져 있는지 구하는 것이 이 글의 목표입니다.
팩토리얼(계승)이란?
팩토리얼은 어떤 수부터 시작해서 1씩 감소시키면서 1이 될 때까지 모든 수를 곱한 값입니다. 기호는 '!'(느낌표)로 표기하며, 0!, 1!, 2!, 3!, 5! 등으로 나타냅니다. 특히 0!과 1!은 항상 1이라는 규칙이 있습니다.
2의 팩토리얼 = 2 × (2-1) = 2 × 1 = 2
3의 팩토리얼 = 3 × (3-1) × (2-1) = 3 × 2 × 1 = 6
예시
입력 − factorial(6)
출력 − factorial(6)의 자릿수: 3
설명 − 6의 팩토리얼 값은 720이고, 720은 세 자리 숫자이므로 결과는 3입니다.
입력 − factorial(12)
출력 − factorial(12)의 자릿수: 9
설명 − 12의 팩토리얼 값은 479001600이고, 이 값은 아홉 자리 숫자이므로 결과는 9입니다.
알고리즘 접근 방식
팩토리얼 값을 직접 계산하면 숫자가 매우 커져 오버플로가 발생하기 쉽습니다. 이를 피하기 위해 로그의 성질을 활용합니다. log10(a × b) = log10(a) + log10(b)라는 성질을 이용하면, 각 수의 log10 값을 더해 전체 팩토리얼의 자릿수를 구할 수 있습니다.
- 팩토리얼을 계산할 수를 입력받습니다.
- 수가 0보다 작으면 음수에는 팩토리얼이 정의되지 않으므로 0을 반환합니다.
- 수가 1 이하이면 1! = 1이며 한 자리 숫자이므로 1을 반환합니다.
- 수가 2 이상이면, 2부터 해당 수까지 반복하는 루프를 만듭니다.
- 루프 밖에서 임시 변수 d를 0으로 초기화하고, 루프 안에서 매 반복마다 d에 log10(i) 값을 더해 나갑니다.
- 반복이 끝나면 floor(d) + 1, 즉 내림한 값에 1을 더해 반환합니다. 로그 값에 1을 더하고 내림하면 해당 수의 자릿수가 됩니다.
- 결과를 출력합니다.
예제 코드
#include <iostream>
#include <cmath>
using namespace std;
// num!에 포함된 자릿수를 반환하는 함수
int count_digits(int num){
// 음수에는 팩토리얼이 존재하지 않음
if (num < 0){
return 0;
}
// 기본 사례(base case)
if (num <= 1){
return 1;
}
// 그 외에는 2부터 num까지 반복하며
// 로그 값을 누적하여 계산
double d = 0;
for (int i=2; i<=num; i++){
d += log10(i);
}
return floor(d) + 1;
}
int main(){
cout<<"number of digits in factorial(1) is: "<<count_digits(1)<< endl;
cout<<"number of digits in factorial(6) is: "<<count_digits(6) << endl;
cout<<"number of digits in factorial(106) is: "<<count_digits(106) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
number of digits in factorial(1) is: 1
number of digits in factorial(6) is: 3
number of digits in factorial(106) is: 171
마무리
이 방법의 가장 큰 장점은 실제 팩토리얼 값을 저장하지 않고도 자릿수를 구할 수 있다는 점입니다. 예를 들어 106!은 171자리에 달하는 거대한 수이지만, 일반적인 int나 long long 자료형으로는 절대 담을 수 없습니다. 하지만 로그를 이용하면 오버플로 걱정 없이 손쉽게 자릿수를 계산할 수 있어, 큰 수의 팩토리얼을 다룰 때 매우 유용한 기법입니다.