[알고리즘/자바] 백준 1676번 - 팩토리얼 0의 개수

 

1676번: 팩토리얼 0의 개수

팩토리얼같은 경우는 결과로 워낙 큰수가 나오기 때문에 다음과 같은 형태로 문제가 많이 나온다.

 

 

팩토리얼 결과중 0의 갯수를 구하는 문제다.

 

0은 2x5일때 발생한다. 그렇기 때문에 팩토리얼을 소인수분해 해서 2x5의 갯수를 구하면 된다.

단, 2는 모든 짝수에 다 들어가지만 5는 모든 홀수에 다 들어가진 않는다.

따라서 2x5의 갯수는 5의 갯수와 같다.

 

구현하면서 25, 125와 같이 5가 2번, 3번 들어가는 숫자들을 잘 처리해줘야한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException{
		
		// 입출력
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String t = bf.readLine();
		int n = Integer.valueOf(t); // n까지 
		
		int ans = 0;
		for(int i=1; i<n+1; i++) {
			
			if(i%5 == 0) { // 5의 배수
				ans +=1; // 5를 무조건 1개는 가짐
				int a = i/5; //5가 더 있는지 검사
				while(a%5 == 0) { // 5의 배수
					a = a/5; 
					ans +=1;
				}
			}
			
		}
		
		bw.write(ans +"\n");
		
	
		bw.flush();
		bw.close();
	}
	
	

		
}