[백준] 정수론및조합론 - 1676번 팩토리얼 0의 개수 java 자바

문제

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

1676번: 팩토리얼 0의 개수

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

 

풀이

0이 늘어나는 경우는 10을 곱했을 때다. 10은 2*5와 같다. 같은 범위의 숫자 내에서 5의 배수보다 2의 배수가 더 많기 때문에 5의 배수의 개수를 세면 된다. (5가 몇 개든 앞에 짝을 지을 2가 있다는 뜻)

그런데 이때 25(5*5)와 125(5*5*5)와 같이 5가 여러번 곱해진 수는 5를 사용하는 개수만큼 10을 만들 수 있다. 따라서 25로는 10을 두개 만들 수 있고 125로는 10을 세개 만들 수 있다.

 

코드

package 정수론및조합론;

import java.util.Scanner;
public class No1676_팩토리얼0의개수 {
	
	public static void main(String args[]) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		System.out.println(solution(n));
	}
	
	public static int solution(int n) {
		int cnt=0;
		if(n==0)
			return cnt;
		
		for(int i=2;i<=n;i++) {
			if(i%5==0) cnt++;
			if(i%25==0) cnt++;
			if(i%125==0) cnt++;
		}
		
		return cnt;
	}
}