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

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

1676번: 팩토리얼 0의 개수

 

방법1

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

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;

        BigInteger big = new BigInteger("1");
        for(int i=1; i<=n; i++){
            big = big.multiply(BigInteger.valueOf(i));
        }
        String s = big.toString();
        for(int i=s.length()-1; i>=0; i--){
            if(s.charAt(i)-'0'==0) cnt++;
            else break;
        }
        System.out.println(cnt);
    }
}

 

내가 생각한 방법은 그냥 직관적으로 팩토리얼을 구한다음 뒤에서부터 0의 개수를 세주는 것이다. 

입력값 n범위가 0에서 500이므로 long형을 넘어선다. 그러므로 bigInteger를 사용한다.

 

 

 

 

방법2

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=1; i<=n; i++){
            int num = i;
            while(num%5==0){
                cnt++;
                num/=5;
            }
        }
        System.out.println(cnt);
    }
}

 

이 방법은 아이디어가 신기했다.

n!은 곱의 계산이기 때문에 0의 개수는 결국 10이 몇번 곱해졌는지 세는 것이다.

10은 2와 5의 곱으로 이루어진다. 

1부터 n까지 for문을 돌며 while문으로 소인수 분해를 해 그 안에 5x2 쌍이 몇개 있는지 찾으면 된다.

이 때,  2는 5보다 작은 수이므로 연속된 수를 곱하게 되면 자연스레 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

따라서 더 작은 개수인 5의 개수에 따라 10의 개수가 결정되므로 소인수 분해를 통해 5의 개수를 알아내면 된다.