백준 10872,1676 - 팩토리얼, 팩토리얼 0의 개수

팩토리얼

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //스캐너보다 성능 나음

        int t = Integer.parseInt(br.readLine());
        Long a = fac(t);
        

        bw.write(a+"");
        bw.flush();
        bw.close();

       }

    private static Long fac(int t) {
        if(t ==0) return 1L;
        else return t*fac(t-1);
    }

}

팩토리얼 0의 갯수

 

실제 팩토리얼을 계산하고 0의 갯수를 세보면 편하겠지만.. 그럴 수 없다

팩토리얼은 조금만 숫자가 커져도 계산하는데 시간이 너무 오래걸린다.

 

-해결방법

 1. 소인수분해 

  뒤에 0이 생기려면, 소인수 중에서 2와 5가 곱해져야함 따라서 2와 5가 몇번 곱해졌는지 

찾을 수 있으면, 0의 갯수를 구할 수 있을 것이다.

가령 8이라면 8! = 8*7*6*5*4*3*2*1 을 소인수 분해하면, 2*5가 하나이므로 8!의 0의 갯수는 1개

        10이라면, 10! = 10*9*8...*1  10이 2*5이므로 2*5가 두개 10!은 0이 두개

소인수분해하면 2가 5보다 많으므로, 5의 갯수만 카운트하면 된다.

하지만 값이 커질 수 록 소인수분해를 해서 2와 5를 찾는과정은 시간도 많이걸리고 복잡할 것이다.

 

2. n/5,+ n/5^2 

 

5의 갯수만 카운트하는 것이라면, n!중에서 5를 인수로 가진 숫자를 세어주면 그만이다.

5를 인수로 가지고 있다는 것은 5의 배수라는 이야기! 

전체를 5로 나누어주면 된다.

이 때 5의 N승의 숫자들은 (25,125..) 5를 두개 혹은 세개씩 가지고 있으므로 이를 인수로 가지고 있는 숫자들도 카운트 해줘야한다. 따라서 

n!의 0의 갯수는  n/5+n/5^2+n/5^3..로 계산할 수 있다.

 

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //스캐너보다 성능 나음

        int t = Integer.parseInt(br.readLine());


       int isFive=0;
        //2n으로 몇번 나눠지는지, 5n으로 몇번 나눠지는지 count하고,min..
        //2가 5보다 더 많음.. 걍 5로 몇번 나눠지는지, 25(5*2) 125(5*3) 몇번 들어가는지 카운트
        for (int j = 5; j <= t; j *= 5) {
                isFive += t/j;
        }


        System.out.println(isFive +" ");
        bw.flush();
        bw.close();

       }



}