# BOJ01676 팩토리얼 0의 개수
https://www.acmicpc.net/problem/1676 (opens new window)
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때 까지 0의 개수를 구한다.
# 팩토리얼의 성질
뒷자리가 0이 나올 수 있는 경우는 2와 5가 곱해졌을 때 10으로 뒷자리는 0으로 끝나는 것을 보장한다. 즉 N!에서 N은 1 ~ N까지의 곱이고, 해당 숫자 중 5의 배수에 따라 0의 개수가 정해진다.
만약 5!인 경우 1, 2, 3, 4, 5로 5의 배수는 5로 유일하다. 실제로 5! = 120으로 0의 개수는 1개이다.
하지만 더 고려해야 할 점이 있다. 25!로 예시를 더 살펴보았다.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25로 5의 배수는 총 5개이다. 하지마 25는 5 x 5로 표현되기 때문에 사실상 0의 개수는 6개가 된다.
정리하면 5의 배수의 개수를 구한 뒤 추가적으로 5의 n제곱 만큼 더해준다.
# 제출 코드
아래는 최종 제출 코드이다.
import java.util.Scanner;
public class BOJ1676 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int count = 0;
while (num >= 5) {
count += num / 5;
num /= 5;
}
System.out.println(count);
}
}