문제 소개
함수 f(x)가 x의 팩토리얼(x!) 값 맨 뒤에 붙은 0의 개수를 반환한다고 가정해 봅시다. 예를 들어 f(3) = 0인데, 이는 3! = 6이라서 끝에 0이 하나도 없기 때문입니다. 반면 f(11) = 2인데, 11! = 39916800처럼 끝에 0이 두 개 붙어 있기 때문입니다.
이제 정수 K가 주어졌을 때, f(x) = K를 만족하는 음이 아닌 정수 x가 몇 개 존재하는지 구하는 것이 목표입니다.
예를 들어 입력이 K = 2라면 정답은 5가 됩니다.
풀이 접근 방법
팩토리얼 값의 끝에 붙는 0은 곱셈 과정에서 2와 5가 한 쌍을 이룰 때마다 생깁니다. 2의 개수는 항상 5의 개수보다 많거나 같으므로, 후행 0의 개수는 결국 인수 5의 개수에 의해 결정됩니다. 이 성질을 활용하면 문제를 효율적으로 해결할 수 있습니다.
먼저 ok(x) 함수를 정의합니다. 이 함수는 르장드르 공식(Legendre's formula)을 이용해 x!에 포함된 5의 개수, 즉 후행 0의 개수를 계산합니다.
- ret := 0으로 초기화합니다.
- i := 5부터 시작해 i <= x를 만족하는 동안 i를 매번 5배씩 키워가며 반복합니다.
- 각 반복마다 ret := ret + x / i를 수행합니다.
- 반복이 끝나면 ret을 반환합니다.
ok(x)는 x가 커질수록 절대 작아지지 않는 단조 증가 함수이므로, f(x) = K를 만족하는 x를 이진 탐색(binary search)으로 빠르게 찾을 수 있습니다. 메인 로직은 다음과 같습니다.
- K가 0이면 5를 바로 반환합니다. (0!부터 4!까지는 모두 후행 0이 없으므로 조건을 만족하는 x가 다섯 개입니다.)
- 탐색 범위를 low := 1, high := K * 5로 설정합니다.
- low < high인 동안 다음을 반복합니다.
- mid := low + (high - low) / 2
- x := ok(mid)
- x < K이면 low := mid + 1, 그렇지 않으면 high := mid
- 최종적으로 ok(low) == K이면 5를, 아니면 0을 반환합니다.
흥미로운 점은 이 문제의 정답이 항상 0 또는 5라는 사실입니다. f(x)의 값은 x가 5의 배수일 때만 증가하고 나머지 경우에는 그대로 유지되기 때문에, 특정 값 K를 만족하는 x가 존재한다면 반드시 연속된 다섯 개의 정수가 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli ok(lli x){
int ret = 0;
for(lli i = 5; i <= x; i *= 5){
ret += x / i;
}
return ret;
}
int preimageSizeFZF(int K) {
if(K == 0) return 5;
lli low = 1;
lli high = (lli)K * 5;
while(low < high){
lli mid = low + (high - low) / 2;
lli x = ok(mid);
if(x < K){
low = mid + 1;
}else high = mid;
}
return ok(low) == K ? 5 : 0;
}
};
main(){
Solution ob;
cout << (ob.preimageSizeFZF(2));
}입력
2
출력
5
복잡도 분석
이진 탐색의 각 단계에서 ok() 함수가 O(log x) 시간에 동작하므로 전체 시간 복잡도는 O(log² K)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.