[Java] BOJ 1676 팩토리얼 0의 개수

문제 

문제 링크 https://www.acmicpc.net/problem/1676

• N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
• 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
• 첫째 줄에 구한 0의 개수를 출력한다.

아이디어

• 0의 개수를 구하려면 10의 개수를 구해야되는데 10은 2 * 5로 이루어져있으므로 2와 5의 개수를 알면 0이 몇개인지 알 수 있다.
• 하지만 여기서 2와 5의 개수를 모두 구할 필요는 없는데, 5의 배수보다 2의 배수가 훨씬 많기 때문에 5의 배수가 있다면 무조건 2의 배수도 있기 때문이다. 
• 따라서 1부터 N까지 5의 배수만 골라 5의 배수를 몇개의 5로 나눌 수 있는지 구하고 그 값을 더해주면 0의 개수가 된다. 

겪은 시행착오

• 5의 배수를 5로 몇번 나눌 수 있는지에 대해 식을 적다가 실수해서 몇번 좀 틀리긴했다... 부끄럽다..

부끄러운 실수다...

코드

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

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

        int N = Integer.parseInt(br.readLine());

        // 뒤에 0이 올려면 곱했을 때 10이 나와야 되는데 10의 개수는
        // 5의 개수로 판별이 되므로 5의 배수가 몇번 나오는지 카운트
        // 5를 곱했을 때 10이 되려면 2도 있어야 되지만
        // 2의 배수가 5의 배수보다 훨씬 많으므로 5의 배수만 신경쓰면 됨
        int five = 0;

        // N이 0일 때, 무조건 출력이 0이므로 0 출력
        if(N == 0){
            System.out.println(0);
        }
        else{
            for(int i = 1; i <= N; i++){
                // i가 0이면 나머지가 0이 나오므로 0을 제외하고 5로 나눴을 때 0일 경우,
                if(i % 5 == 0){
                    // i를 직접적으로 건드리면 무한루프에 빠지므로 따로 변수에 i값을 저장해줌
                    int num = i;

                    // 기존 5를 카운트 하는 변수에 i를 5로 먗반 나눌 수 있는지 더함
                    while(true){
                        // i를 5로 계속 나눌 수 있을 경우
                        if(num != 0 && num % 5 == 0){
                            num = num / 5;
                            five = five + 1;
                        }
                        // 5로 계속 나눌 수 없을 경우
                        else{
                            break;
                        }
                    }
                }
            }

            System.out.println(five);
        }
    }
}