문제 소개
하나의 숫자 Y가 주어졌을 때, X!(X 팩토리얼)의 끝자리에 0이 최소 Y개 이상 포함되도록 만드는 가장 작은 수 X를 구하는 것이 이 글의 목표입니다.
예를 들어 Y = 2라고 가정해 보겠습니다. 이때 정답은 X = 10입니다. 10! = 3,628,800이며, 이 숫자는 끝자리에 0이 정확히 2개 있기 때문입니다.
해결 접근 방식
이 문제는 이진 탐색(Binary Search)을 활용하면 매우 효율적으로 해결할 수 있습니다.
N!의 후행 0(끝자리 0)의 개수는 N!을 구성하는 인수 중 5의 개수와 같습니다. 그 이유는 10 = 2 × 5이고, 팩토리얼 계산 과정에서 2는 5보다 항상 더 자주 등장하기 때문에 0의 개수는 사실상 5의 개수에 의해 결정되기 때문입니다.
또한 후행 0의 개수가 Y를 넘지 않아야 하므로, X는 항상 [0, 5×Y] 범위 안에 존재합니다. 따라서 이 범위에서 이진 탐색을 수행하면 원하는 X를 빠르게 찾을 수 있습니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int factorCount(int n, int X) {
if (X < n)
return 0;
return (X / n + factorCount(n, X / n));
}
int findX(int Y) {
int left = 0, right = 5 * Y;
int N = 0;
while (left <= right) {
int mid = (right + left) / 2;
if (factorCount(5, mid) < Y) {
left = mid + 1;
}else {
N = mid;
right = mid - 1;
}
}
return N;
}
int main() {
int Y = 4;
cout << "Smallest value of X: " << findX(Y);
}실행 결과
Smallest value of X: 20
코드 설명
- factorCount(n, X): X! 안에 인수 n이 몇 번 포함되어 있는지 재귀적으로 계산합니다. X를 n으로 반복해서 나누며 누적하는 방식으로, 르장드르 공식(Legendre's formula)과 동일한 원리입니다.
- findX(Y): [0, 5×Y] 범위에서 이진 탐색을 수행합니다. mid 지점의 후행 0 개수가 Y보다 작으면 탐색 범위를 오른쪽으로, 크거나 같으면 왼쪽으로 좁혀가면서 조건을 만족하는 가장 작은 값을 추적합니다.
- main(): Y = 4인 경우를 테스트합니다. 20! = 2,432,902,008,176,640,000으로 끝자리 0이 정확히 4개 있고, 19!는 0이 3개뿐이므로 20이 정답이 됩니다.
시간 복잡도
이진 탐색의 각 단계에서 후행 0의 개수를 계산하는 데 O(log X)의 시간이 걸리고, 탐색 범위가 5×Y이므로 전체 시간 복잡도는 대략 O(log²Y) 수준으로 매우 효율적입니다. 덕분에 Y가 큰 값이라도 빠른 시간 안에 답을 구할 수 있습니다.