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

문제

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

입력

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

출력

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

입력 예시 1

10

출력 예시 1

3

아이디어

팩토리얼은 1부터 N까지의 자연수 곱을 일컫습니다. 일례로 5! = 1 x 2 x 3 x 4 x 5, 7! = 1 x 2 x 3 x 4 x 5 x 6 x 7 등이 있습니다.

팩토리얼은 25만 넘어가도 그 수가 10의 25승이 넘게 됩니다. 하지만 문제에서는 0부터 500까지의 수가 입력될 수 있으며, 자바는 매우 큰 수를 효과적으로 처리하지 못하므로 우리는 다른 방식으로 팩토리얼에 접근할 필요가 있습니다. 

 

뒤에서부터 0이 나오려면 어떻게 해야 할까요? 바로 10이 곱해지면 됩니다. 예를 들어 1234 에 곱하기 1000을 하면 1234000이 됩니다. 따라서 우리는 팩토리얼을 곱할 때 만들어지는 10의 개수를 찾으면 됩니다. 

 

10은 2와 5의 곱으로 이루어져 있습니다. 우리는 2와 5의 쌍을 찾으면 쉽게 0의 개수를 구할 수 있습니다. 따라서 반복해서 수가 입력될 때, 해당 수를 소인수 분해하여 2와 5의 개수를 카운트 합니다. 반복문이 끝나면 2와 5의 개수를 조합하여 10이 만들어지는 조합을 출력합니다. 더 이상의 설명은 코드로 찾아뵙겠습니다.

코드

import java.util.*;

public class Main {
    static int twoCnt, fiveCnt;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for (int i = 1; i <= N; i++) {
            int tmp = i;
            while (tmp % 2 == 0) {
                twoCnt++;
                tmp /= 2;
            }
            while (tmp % 5 == 0) {
                fiveCnt++;
                tmp /= 5;
            }
        }
        System.out.println(fiveCnt > twoCnt ? twoCnt : fiveCnt);
    }
}