[코딩테스트/백준 알고리즘] 1676번 : 팩토리얼 0의 개수 (자바, Java 풀이)

문제

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

1676번: 팩토리얼 0의 개수

---

문제 설명

---

문제 풀이

 n!의 뒤에 0이 몇 개 나오는지 알아보기 위해선 그 수를 소인수분해 했을 때 2와 5의 쌍이 몇 개 나오는지 알아보면 된다. 하지만 2는 엄청나게 많이 나올 것이 분명하기 때문에 우리는 5가 몇 개 나오는 지만 신경쓰면 된다.

수	소인수 분해	n!
4!	4 X 3 X 2 X 1 = 2³ X 3	24
5!	5 X 4 X 3 X 2 X 1 = 2³ X 3¹ X 5¹	120
10!	10 X 9 X 8 X 7 X 6 X 5 X 4 X 3 X 2 X 1 = 2⁸ X 3⁴ X 5² X 7	3,628,800
15!	15 X 14 X 13 X 12 X 11 X 10 X 9 X 8 X 7 X 6 X 5 X 4 X 3 X 2 X 1 = 2¹¹ X 3⁶ X 5³ X 7² X 11 X 13	1,307,674,368,000

 

0의 개수 계산

        for(int i = 1; i <= N; i++) {
            if(i % 5 == 0) {
                int temp = i;
                while(temp % 5 == 0) {
                    five++;
                    temp /= 5;
                }
            }
        }

1부터 n까지 수를 증가시키면서 그 수가 5로 나누어 떨어지는지, 나누어 떨어진다면 몇 번 나누어떨어지는지 계산하며 5의 개수를 구한다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        int N = new Scanner(System.in).nextInt();
        int five = 0;
        
        for(int i = 1; i <= N; i++) {
            if(i % 5 == 0) {
                int temp = i;
                while(temp % 5 == 0) {
                    five++;
                    temp /= 5;
                }
            }
        }
        System.out.println(five);
    }
}