(16) [C++, Java] 백준 No.1676 : 팩토리얼 0의 개수

문제

풀이

자세한 풀이 : 

 

# C++(나의 풀이)
- 팩토리얼을 펼쳤을 때 각각의 수를 소인수분해 해서 5의 개수를 셈
- 이것보다는 백준 풀이가 훨씬 간단하다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> vec;

    for (int i = 1; i <= n; i++)
    {
        int num = i;

        for (int j = 2; j * j <= i; j++)
        {
            while (num % j == 0)
            {
                vec.push_back(j);
                num = num / j;
            }
        }

        if (num > 1)
            vec.push_back(num);
    }

    cout << count(vec.begin(), vec.end(), 5) << endl;
}

# C++(백준 풀이)
- 1~N까지의 숫자에서  5^1 = 5의 배수, 5^2 = 25의 배수, 5^3 = 125의 배수, 5^k이 n보다 작을 때 까지 이들의 개수를 구함.
- 이 개수는 N / 5^1 + N / 5^2 + N / 5^3 + ... 이런 방식으로 구할 수 있음.  

#include <iostream>

using namespace std;

int main() {
    int ans = 0;
    
    int n;
    cin >> n;
    
    for (int i=5; i<=n; i*=5)
        ans += n/i;
        
    cout << ans << '\n';
}

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i=5; i<=n; i*=5) {
            ans += n/i;
        }
        System.out.println(ans);
    }
}