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

 

팩토리얼 계산 후 숫자 맨 뒤에 연속적으로 존재하는 0의 개수를 출력하는 문제이다.

 

10을 입력하면 10!을 계산한다.

10! = 3628800

이므로 2가 출력된다.

 

뒷자리가 0이 나오려면 그 수에 2와 5가 곱해져 있어야 한다.

= 소인수분해 시 2X5가 짝지어서 존재한다.

 

조금 더 생각해 보면 

팩토리얼은 연속된 값을 곱하기 때문에 5의 개수보다 2의 개수가 많을 것이다.

 

예를 들어 8!은 8x7x6x5x4x3x2x1이고

소인수분해를 해 보면 5는 1개, 2는 6개이다.

 

따라서 문제에서 요구하는 0의 개수는

주어진 수에서 포함된 5의 개수와 똑같다는 것이다.

 

5의 개수는 5로 계속 나누면 구할 수 있다.

 

 

package boj;

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // N 입력
        int N = Integer.parseInt(br.readLine());
        // 5의 개수를 저장할 변수
        int count = 0;
        
        // N이 5보다 크거나 같을 경우에 반복
        while(N >= 5) {
        	count += N / 5;
        	N /= 5;
        }
        
        sb.append(count);
        System.out.println(sb);
        
        


    }
   
}