1676. 팩토리얼 0의 개수

저는 무식하게 팩토리얼을 전부 구한뒤, 문자를 뒤집고 0의 갯수를 세는 무식한 방법을 떠올렸는데,

이렇게 하니까 출력초과(overflow?) 혹은 틀렸다고 나오더군요. 아무래도 500팩토리얼까지 나오려면 힘들었나 봅니다.

 

결국 답을 찾아봤는데, 생각보다 간단했습니다.

0의 갯수 = 인수분해를 했을때 10의 제곱수 = 소인수분해를 했을때 2와 5의 제곱수 중 최솟값.

팩토리얼은 순차적으로 곱해지므로, 텀이 짧은 2가 당연히 더 많을 수 밖에 없고, 따라서 5의 제곱수만 구하면 됩니다.

주의할 점은, 5의 제곱수에 해당할때는 5가 더 출몰(?) 한다는 점...

가령 24! 까지는 5, 10, 15, 20에서 각각 등장하여 5^4이지만, 25!부터는 25=5^2이라 5^6이 되어버립니다.

그점만 조심하면 되겠습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Java1676 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int count = 0;
		
		while (n>=5) {
				count += n/5;
				n /= 5;
		}
		System.out.println(count);
	}
}