[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. 코드

1. 풀이 [Java]

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);
    }
}

2. 풀이 [C++]

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

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

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

---