이 글에서는 임의의 수 n에 대해 n!의 결과값 끝에 붙는 0, 즉 후행 0(trailing zeros)의 개수를 구하는 방법을 알아봅니다.
예를 들어 n = 5이면 5! = 120이므로 후행 0은 1개입니다. 20! = 2432902008176640000이므로 후행 0은 4개입니다.
단순 계산 방식의 한계
가장 직관적인 방법은 실제로 팩토리얼 값을 계산한 뒤 0의 개수를 세는 것입니다. 하지만 이 방법은 n이 조금만 커져도 자료형의 오버플로우 때문에 사용할 수 없습니다. 따라서 팩토리얼을 직접 계산하지 않고도 답을 구할 수 있는 수학적 접근이 필요합니다.
핵심 아이디어: 소인수 2와 5
수가 10으로 나누어떨어지려면 소인수로 2와 5를 동시에 가져야 합니다. 즉, 후행 0은 팩토리얼의 소인수 중 2와 5가 짝지어지는 만큼 생깁니다.
여기서 중요한 점은 n!의 소인수 분해에서 2의 개수가 항상 5의 개수보다 많거나 같다는 사실입니다. 따라서 후행 0의 개수는 곧 소인수 5의 개수와 같습니다.
Trailing 0s = Count of 5s in prime factors of factorial(n)
소인수 5의 개수는 5의 거듭제곱들이 n 이하에서 몇 번 등장하는지 세면 되므로 다음과 같은 공식으로 표현할 수 있습니다.
Trailing 0s = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...
예를 들어 n = 20이라면 ⌊20/5⌋ = 4, ⌊20/25⌋ = 0이므로 후행 0은 총 4개입니다.
알고리즘 단계
- count를 0으로 초기화합니다.
- i = 5부터 시작하여 n / i ≥ 1인 동안 i를 5배씩 늘려가며 반복합니다.
- 각 반복마다 count에 n / i의 몫을 더합니다.
- 최종적으로 count를 반환합니다.
C++ 구현 예제
#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
int countTrailingZeros(int n) {
int count = 0;
for (int i = 5; n / i >= 1; i *= 5)
count += n / i;
return count;
}
main() {
int n = 20;
cout << "Number of trailing zeros: " << countTrailingZeros(n);
}실행 결과
입력: n = 20
출력: Number of trailing zeros: 4
정리
이 방법은 팩토리얼을 실제로 계산하지 않기 때문에 n이 매우 큰 경우에도 오버플로우 없이 빠르게 후행 0의 개수를 구할 수 있습니다. 시간 복잡도는 O(log₅ n)으로 매우 효율적이며, 코딩 테스트나 알고리즘 문제에서 자주 등장하는 대표적인 최적화 기법입니다.