[백준] 1676 : 팩토리얼 0의 개수 JAVA 풀이

 

처음에는 n을 입력받고 팩토리얼값을 구한 뒤

뒤에서부터 0의 개수를 세려고 했다.

하지만 n이 커질 경우 BigInteger 클래스를 사용하지 않고서는 담을 수 없는 경우가 발생하게 된다.

그래서 다른 해결방법이 있을 것 같아 서치를 하다 이 포스트를 발견했다.

 

https://st-lab.tistory.com/165

[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]

 

소인수분해를 했을 때 2와 5가 존재하면 뒷자리는 0으로 끝나게 된다.

즉 어떤 수를 소인수분해했을 때, 2와 5가 짝을 이루는 쌍의 개수 = 뒷자리 0의 개수가 되는 것이다.

 

그리고 2는 항상 5보다 많이 곱해져있기 때문에

2와 5가 짝을 이루는 쌍의 개수 = 5가 등장하는 횟수가 된다.

 

2와 5가 짝을 이룰 때만 0이 하나씩 증가하는 것이니

5의 배수가 아닌 값들은 고려할 필요가 없다.

 

예를 들어 n이 25라면 5 10 15 20 25만 고려하면 된다.

5 10 15 20 25 각각의 수를 소인수분해했을 때 5의 출현빈도는

1 1 1 1 2가 되고,

25!에서 뒷자리 0의 개수는 1+1+1+1+2 = 6이 된다.

 

1부터 n까지의 숫자들 중 5의 배수인 것들만 골라내고

5의 배수인 그 수를 소인수분해 했을 때 5가 몇 개나 있는지 누적합을 구해주면 된다.

 

 

import java.io.*;
import java.util.*;
public class Main {

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