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

문제

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

문제 풀이

나는 맨 처음에 다음과 같이 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Stream;

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

        int n = Integer.parseInt(br.readLine());
        int f = 1;
        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            f *= i;
        }

        int[] arrNum = Stream.of(String.valueOf(f).split("")).mapToInt(Integer::parseInt).toArray();

        for (int i = arrNum.length - 1; i >= 0; i--) {
            if (arrNum[i] == 0)
                cnt++;
        }
        System.out.println(cnt);

        br.close();
    }
}

 

많은 케이스들을 테스트해 본 결과 정확히 값들이 나왔다.
하지만 내 코드에는 치명적인 문제점이 하나 있었다.

 

바로 int형은 최대 21억까지만 저장할 수 있는데, 13! 같은 경우 6,227,020,800의 값이 나오기 때문에 이미 초과된다.

 

즉, n이 조금만 커져도 잘못된 숫자가 나오게 된다.

 

그래서 도움을 받고 코드를 다음과 같이 짰다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int cnt = 0;
        for (int i = 5; i <= n; i *= 5) {
            cnt += n / i;
        }

        System.out.println(cnt);
        br.close();
    }
}

 

사실 이 코드를 이해하기까지 시간이 꽤 걸렸다.

        for (int i = 5; i <= n; i *= 5) {
            cnt += n / i;
        }

 

이 부분이 핵심 로직인데 이에 대해 자세히 알아보자.

 

팩토리얼 끝에 있는 0의 개수는 10이 몇 번 곱해졌는지를 의미한다.
즉, 2와 5가 짝을 이루면 0이 하나 생긴다.
여기에서 한가지 방법을 떠올릴 수 있다.
바로 2의 개수를 세는 것이다.

 

하지만 2는 너무 많기 때문에 5의 개수만 세면 된다.
이 부분이 가장 어려웠던 것 같다.

 

예시를 들어 설명하자면
25! 같은 경우 이 안에 5는 25 / 5 = 5, 즉, 5의 배수인 숫자가 5개 들어있다.
25는 5 x 5이기 때문에 5가 한 번 더 있다. (25 / 25 = 1)
그래서 총 6개의 5가 들어있고, 2와 짝지으면 그만큼 0이 생기게 된다.

 

정리하자면 2는 항상 많고, 5는 5의 배수 개수만큼 존재하기 때문에 5는 제한적이다.
따라서 2와 5가 짝을 이뤄 만든 10의 쌍은 결국 5의 개수에 좌우된다.

 

이번 문제는 나에게 있어 꽤나 어려웠던 문제였던 것 같다.
문제 질의 자체는 간단하나, 해당 문제의 원리를 이해하기에는 아직 부족한 것 같다.