[백준]1676 - 팩토리얼 0의 개수 문제 풀이(Java,자바)

코드

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int result = 0;
        for (int i = 5; i <= n; i *= 5) {
            result += n / i;
        }
        
        System.out.println(result);
    }

 

풀이

오해할 수 있는 점

처음 문제를 대충 보고 String을 char array로 변환해서 0을 세는 방식으로 구현했다.

하지만 이 경우엔 N이 최대 500까지 올라가므로 double의 범위를 초과하기 때문에 실패한다.

그러므로 다른 방식으로 접근해야 한다.

 

팩토리얼 계산은 필요가 없다

0의 개수는 결국 팩토리얼안에서 5와 2의 곱으로 인해 발생한다.

즉, 5와 2의 개수를 찾으면 자연스럽게 0을 도출할 수 있다.

하지만, 2는 5에 비해 훨씬 많으므로 5를 위주로 찾으면 바로 답을 구할 수 있다.

 

n 이 25라고 가정한다면

25를 먼저 5로 나눈다. 그러면 5가 5개 있다는 것을 의미한다.

25! 는 5, 10, 15, 20, 25를 가지고 있다.

여기서 문제는 25는 5가 2개인 것이다. 따라서 반복문을 통해 25를 또 나눠줌으로써 해결한다.

 

25 / 5 = 5

25 / 25 = 1

결론 : 6개

 

최종적으로 답을 구할 수 있다.