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

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

1676번: 팩토리얼 0의 개수

 

---

• 문제

 

 

---

• 문제 풀이

백준 1676번 팩토리얼 0의 개수는 실버 4 난이도의 수학 문제이다. 문제 자체는 되게 간단하다. 우선 팩토리얼 n, 즉 n! 을 구한다. 그리고 n! 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구해서 출력만 해주면 된다. 

 

예를 한번 보겠다.

3! = 3 × 2 × 1 = 6. 따라서 0이다.

4! = 4 × 3 × 2 × 1 = 24. 따라서 0이다.

5! = 5 × 4 × 3 × 2 × 1 = 120. 마지막에 0이 1개가 있으므로 1이다.

 

이 문제는 BigInteger, 즉 큰 정수를 이용해서 접근할 것이다. BigInteger에 대해 잘 모르면 밑에 있는 링크를 참고해주면 되겠다.

 

https://propercoding.tistory.com/33

[알고리즘] 큰 숫자 (정수) BigInteger 사용법 - JAVA [자바]

 

우선 BigInteger로 n! 을 구한다. BigInteger를 이용함으로써 숫자의 범위는 신경 쓰지 않아도 된다. 그리고 n! 을 구했으면 n! 을 10으로 나눴을 때 나머지가 0인 개수를 구하면 된다.

 

---

• 코드

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;
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());
        BigInteger fac = new BigInteger("1");
        for (int i = 2; i <= n; i++) {
            fac = fac.multiply(new BigInteger(Integer.toString(i)));
        }
        int count = 0;
        while (true) {
            BigInteger num = fac.remainder(new BigInteger("10"));
            if (num.equals(new BigInteger("0"))) {
                count++;
            } else {
                break;
            }
            fac = fac.divide(new BigInteger("10"));
        }
        System.out.print(count);
    }
}

 

---

• 후기

이 문제는 실은 예전에 군대에 있을 때 코딩 동아리에서 배운 문제였다. 그때는 이 문제를 못 풀고 나중에 더 배우고 나면 풀어야지 생각하다 이번에는 BigInteger를 이용해서 풀게 되었다.