[BOJ] 백준 1676 팩토리얼 0의 개수 (Java)

 

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

N!에서 뒷자리부터 0의 갯수를 출력하는 문제 (0! = 1)

(단, '0'이 아닌 숫자가 나오는 지점까지의 갯수)

0 ≤ N ≤ 500이므로 크지 않은 N이지만 N!는 long 타입으로 담을 수 없다.

그렇기에 규칙을 파악하여 N! 결과값이 아닌 팩토리얼 과정에서 규칙을 파악해야 한다.

0! = 1

1! = 1 

2! = 2 

3! = 6 

4! = 24 

5! = 120 

6! = 720

7! = 5040 

8! = 40320 

9! = 362880 

10! = 3628800

▶ 0 개수는 결국 10의 배수이며 2*5의 구성이 나오는 경우이다.

즉, N! 과정에서 2와 5로 나누어 떨어지는 경우를 count 한다.

 

주의해야할 Case

[input]
0
 
[output]
0

---

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
                 
        int cnt_of_2 = 0;
        int cnt_of_5 = 0;
         
        // factorial 진행과정 중에서 2와 5의 곱의 개수를 파악한다.
        for(int i=1; i<=N; i++) {
            int target = i;
             
            // 소인수 분해하며 2의 개수를 파악한다.
            while((target % 2 == 0)) {
                cnt_of_2++;
                target = target / 2;
            }
             
            // 소인수 분해하여 5의 개수를 파악한다.
            while((target % 5 == 0)) {
                cnt_of_5++;
                target = target / 5;
            }
        }
         
        System.out.println(Math.min(cnt_of_2, cnt_of_5));
    }
}