문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

풀이

N의 범위가 500이하라서 500일 때 팩토리얼 수는 엄청엄청 큰 수임을 알 수 있다. 따라서 일반적인 팩토리얼 구하는 방식으로는 구할 수 없다.

문제는 0의 개수를 찾는 것이다. 이는 2와 5로 이루어 져있으면 0이 나오게 되고 2와 5를 몇번 하는지 찾는 것과 같다. 왜냐하면 0이 나오려면 2와 5를 이용하는 방법 밖에 없기 때문이다. 즉, 해당 수를 소인수 분해 했을 때 2와 5의 갯수 중 제일 작은 것을 출력하면 된다. 하지만 2는 5보다 작아서 어떻게든 5의 갯수보다 많이 나올 것이다. 따라서 5의 개수만 찾아주면 되는데, 25와 같이 5를 한번 더 사용하는 수가 존재한다. 이 부분을 유의해서 해결해 주면 된다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int count = 0;

		while (n >= 5) {
			count += (n / 5);
			n /= 5;
		}

		System.out.println(count);
	}

}