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

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

1676번: 팩토리얼 0의 개수

 

Problem

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

 

Input

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

 

Output

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

 

Insight

1. 팩토리얼 N = 1*2*3*4*5*...*N-1*N 

2. 여기서 10을 만들 수 있는 조합은 2*5

3. 2와 5의 곱이 한 개가 나올 때마다 0의 갯수가 하나씩 늘어남

4. 5는 무조건 2보다 적거나 같게 나오기 때문에 입력한 N에서 5의 배수가 있을 때 마다 카운트 해준다. 

6. 25는 5가 2번 포함, 125는 5가 3번 포함이므로 포함된 숫자만큼 카운트를 한 번씩 더 해준다. 

 

<Process> 
1. 입력된 n을 5로 나눠주어 나온 몫만큼 카운트
2. 5^x 에서 x를 늘려가면서 더이상 5^x 로 n이 안 나눠질때까지 몫을 카운트

 

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

public class Main {
    
    public static void main(String[] args) throws IOException{ 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int total=0, cnt=0, i=5; 
        while(true){
            cnt = n/i; 
            total+=cnt; 
            i*=5; 
            if(cnt == 0){break;}
        }
       
        bw.write(String.valueOf(total));
       
        bw.flush();
        bw.close();
    }
}