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

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

 

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

---

1.  아이디어

 

곱셈에서 0의 개수는 소인수 분해를 했을 때 2의 개수와 5의 개수 중 적은 값과 같다.

팩토리얼에서는 5의 개수가 2의 개수보다 적거나 같으므로 5의 개수를 세면 된다.

---

2. 문제풀이

 

N이 최대 500이므로 1부터 N까지 순회하며 5의 배수일 때, 25의 배수일 때, 125의 배수일 때 각각 1, 2, 3을 더하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;

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++) {
            if (i % 125 == 0) cnt += 3;
            else if (i % 25 == 0) cnt += 2;
            else if (i % 5 == 0) cnt += 1;
        }

        System.out.println(cnt);
    }
}

---

4. 후기