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

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

백준 1676 팩토리얼 0의 개수 자바 풀이

소인수 분해의 성질을 이용하여 끝에 0이 얼마나 오는지 푸는 문제이다.

1! = 1

2! = 1*2

3! = 1*2*3

4! = 1*2*3*4

5! = 1*2*3*4*5

6! = 1*2*3*4*5*6

7! = 1*2*3*4*5*6*7

8! = 1*2*3*4*5*6*7*8

9! = 1*2*3*4*5*6*7*8*9 

10! = 1*2*3*4*5*6*7*8*9*10

팩토리얼을 보면 무조건 5가 있을 경우 2보다 갯수가 적다.

이를 이용하여 num이 5보다 큰 경우, num의 몫의 누적합 갯수를 구하면, 0의 갯수가 나온다.

 

코드

import java.util.*;

public class back1676 {

    public static void main(String args[]){

        Scanner scanner=new Scanner(System.in);

        int num=scanner.nextInt();

        int count=0;

        while(num>=5){

            count+=num/5;

            num/=5;

        }

        System.out.println(count);

    }

}