(JAVA)백준온라인 1676번 - 팩토리얼 0의 개수

맨 처음에는 그냥 팩토리얼을 다 구한다음 뒤에서 0 갯수를 세고 0이 아닌 문자열이 나오면 바로 break로 탈출해서 갯수를 출력하는 형식으로 했었다. 하지만 숫자가 너무 커져서 감당을 할 수 없어서 정상적인 결과가 나오지 않아서 검색을 해보았더니 정말 기발한 방법이 있었다

마지막에 0이 나온다는것은 2x5 조합이 있다는 것이다 그리고 2는 모든 짝수의 소인수가 될 수 있어서 2의 개수는 정말 많다 그러므로 5의 갯수만 구해주면 끝나는 것이다 이것의 알고리즘을 적어보자면

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int count = 0;

        //ex) 10을 입력 할 경우? 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
        //여기서 2 x 5 의 조합이 되는 경우는 맨 앞에 있는 10과 하나하나씩 있는 5와 2가 있다 그러므로 2개
        for (int i = 5; i <= n; i *= 5) {
            count += n / i;
        }

        System.out.println(count);
    }
}

이런 방법이 있었다...! 정말 나는 아직 많이 부족하다