백준 1676 팩토리얼 0의 개수

1. 문제

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

입력

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

출력

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

예제 입력 1 복사

10

예제 입력 2 복사

3

 

2 - 1. 나의 풀이

30! 정도 넘어가면 숫자가 너무 커서 long형에 저장되지 않는다.

그렇다면 어떤 규칙이 있겠구나 싶었는데 그 규칙을 찾지 못했다.

구글링을 통해 매우 큰 수를 저장할 수 있는 BigInteger 클래스를 사용해서 풀었다. (정수는 BigInteger)

뒤에서부터 처음 0이 아닌 숫자를 세면 된다.

 

2 - 2. 나의 코드

package solvedac;
import java.math.BigInteger;
import java.util.*;

public class ac1676 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count =0;

        BigInteger bigNum = new BigInteger("1");

        for (int i = 1; i <= n; i++) { //i <= n 으로 해야 n까지 곱해진다.
            bigNum = bigNum.multiply(new BigInteger(Integer.toString(i)));
        }
        String num = bigNum.toString();
        for (int i = num.length() - 1; i > 0; i--) {
            if(num.charAt(i) == '0') count++;
            else break;
        }
        System.out.println(count);

    }

}

 

3 - 1. 다른 풀이

 내가 찾지 못한 규칙을 다른 분이 찾았다.

규칙의 키 포인트는 5의 존재이다.

2와 5가 곱해지면 자연스럽게 뒷자리가 0이 만들어 진다. 2는 5 이전에 항상 있으므로

소인수 분해 했을 때 5의 개수를 세어주면 된다.

 

 

3 - 2. 다른 코드

package solvedac;
import java.util.*;

public class ac1676_sol {

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

        while(n >= 5){
            cnt += n / 5;
            //25, 50, 75, 100, 125 이상의 수는 5로 한번 나눠도 인수로 5가 또 있기 때문에
            //while문을 통해 다시 누적합 해줘야한다.
            n /= 5;
        }
        System.out.println(cnt);
    }
}

 

4. 얻어갈 점, 참고 블로그

1. BigInteger 사용법

https://coding-factory.tistory.com/604

[Java] 큰 숫자(정수) 다루기 BigInteger 사용법 & 예제 총정리

 

2. 규칙성 찾기

https://st-lab.tistory.com/165

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