백준11687_팩토리얼0의 개수
2022.01.06
문제
접근 방법
- M의 크기가 작다면, 1부터 최대값까지 탐색하면서 0의 개수를 세주면 된다. 하지만, 해당 문제에서는 M의 크기가 크기 때문에 불가능하다.
- N! 에서 0의 개수를 세려면, 2*5 의 수를 세면 된다. 즉, 2와 5의 개수를 구하면 되는데, 5의 개수가 더 적을테니 5의 개수를 구하면 된다.
그러면 N!에서 5의 개수는 어떻게 구하나?
N!의 약수 중에서 5, 25, 125… 로 나누어 떨어지는 수를 구하면 된다.
최종적으로, 해당 문제에서는 M의 최대 크기가 1억이기 때문에 1 ~ 5억까지의 수를 계산해보면 된다. 단, 시간 초과를 고려하여 이분탐색으로 정답을 찾아야한다.
소스 코드
import java.util.Scanner;
public class Main {
private static final int MAX = 100000000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int targetZeroCount = sc.nextInt();
System.out.println(solve(targetZeroCount));
}
private static int solve(int targetZeroCount) {
int left = 1;
int right = MAX * 5;
int answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 5; i <= mid; i *= 5) {
count += mid / i;
}
if (count < targetZeroCount) {
left = mid + 1;
} else {
if (count == targetZeroCount) {
answer = mid;
}
right = mid - 1;
}
}
return answer;
}
}