[BaekJoon] #1676 - 팩토리얼 0의 개수 [Java][C++]

문제 링크

---

1. 아이디어

$N!$에서 뒤에 나온 0의 개수를 구하는 문제로 뒤에 0이 나온다는 것은 2와 5를 소인수로 가진다는 의미다. 팩토리얼은 1부터 $N$까지 쭉 곱해서 만들어지는데, 이때 소인수로 2의 개수가 항상 5의 개수보다 많거나 같아서 $N!$에서 뒤에 나온 0의 개수는 $N!$의 소인수 중 5의 개수와 같다. $N$이 최대 500이고 5의 배수들은 기본적으로 5 한 개를 소인수로 갖는데 25의 배수는 5 두 개를 소인수로 갖고, 125의 배수는 5 세 개를 소인수로 갖는다. 따라서 $N$을 5로 나눈 몫, 25로 나눈 몫, 125로 나눈 몫으로 소인수로 갖는 5의 개수를 구할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++]

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());
        System.out.println(n / 5 + n / 25 + n / 125);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    cout << n / 5 + n / 25 + n / 125;
}

---