백준 1676 / 팩토리얼 0의 개수

문제

풀이

설명

N!의 0의 개수가 몇개인지 알아내는 문제
N!의 0의 개수를 알아내려면 N!을 소인수분해 했을 때, 2와 5가 몇 개 나오는지 알아야 한다.
5의 개수가 항상 2의 개수 보다 적기 때문에, 5의 개수만 세어주면 된다.
N! 0의 개수 = [N/5]+[N/5^2]+[N/5^3]+...

ex1) 10! = 3628800
10!의 0이 2개 이므로 2를 출력하게 해야한다.
여기서 10!의 0이 2개인 이유는 10!을 소인수분해 해보면 알 수 있다.
10! = 1X2X3X4X5X6X7X8X9X10
= 1X2X3X2^2X5X2X3X7X2^3X3^2X5
= 2^8X3^4X5^2x7
5의 2제곱이므로 0이 2개이다

ex2) 100!의 경우
인수로 5가 들어가는 것 중 25, 50, 75, 100은 각각 5가 두 개씩 들어간다.
따라서 100/5를 해서 세는 5의 개수 = 20, 여기서 25,50,75,100의 5 하나를 세고 100/25를 한번 더 해서 5의 개수를 한번 더 세어줘야 한다.
결론은 100!의 0의 개수는 20+4 = 24 가 된다.

코드

public class Num1676 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int ans = 0;
		for (int i=5; i<=N; i*=5) {
			ans += N/i;
		}
		System.out.println(ans);
	}
}

출처 : https://www.acmicpc.net/problem/1676