문제 소개
숫자 n이 주어졌을 때, n!(팩토리얼) 값 끝에 붙어 있는 0(후행 0)의 개수를 구하는 것이 목표입니다.
예를 들어 n = 20이라면, 20! = 2432902008176640000이므로 후행 0은 총 4개이며, 따라서 출력값은 4가 됩니다.
접근 방법
후행 0은 곱셈 과정에서 10이 만들어질 때마다 하나씩 생깁니다. 10 = 2 × 5이므로, 팩토리얼을 구성하는 소인수 중 2와 5가 짝지어지는 횟수가 곧 후행 0의 개수입니다. 팩토리얼에서는 2의 개수가 항상 5의 개수보다 많기 때문에, 5가 몇 번 등장하는지만 세면 됩니다.
단, 25 = 5², 125 = 5³처럼 5의 거듭제곱 수들은 한 번에 여러 개의 5를 기여하므로 이를 모두 고려해야 합니다. 해결 절차는 다음과 같습니다.
- 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);
}입력
20
출력
Number of trailing zeros: 4
복잡도 분석
이 알고리즘은 반복할 때마다 i가 5배씩 증가하므로 시간 복잡도는 O(log₅ n), 즉 사실상 O(log n)입니다. n이 아무리 커도 실제 팩토리얼 값을 직접 계산하지 않고도 후행 0의 개수를 매우 빠르게 구할 수 있다는 점이 이 방법의 가장 큰 장점입니다.