백준 1676번 C++

백준 1676번 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    int exp_two=0,exp_five=0;
    int ans = 0;
    cin>>N;

    for(int i=1;i<=N;i++)
    {
        int tmp = i;
        if(tmp%5==0) 
        {
            while(tmp%5==0)
            {
                exp_five++;
                tmp/=5;
            }
            /*
             while(tmp)
            {
                if(tmp%5==0) exp_five++;
                tmp/=5;
            }
            */
        }

        else if(tmp%2==0) 
        {
            while(tmp%2==0)
            {
                exp_two++;
                tmp/=2;
            }
            /*
            while(tmp)
            {
                if(tmp%2==0) exp_two++;
                tmp/=2;
            }
            */
        }
    }

    if(exp_two < exp_five) ans = exp_two;
    else ans = exp_five;

    cout<<ans;

    return 0;
}

문제 풀이

수학적으로 접근해야 하는 문제입니다. 처음에는 단순히 5의 배수일때마다 결과값이 1이 추가된다고 생각했지만 잘못된 생각이였습니다. 0이 생길려면 10을 곱해야 하고 10은 2나 5를 곱해야 합니다. N!을 소인수분해 하였을 때 2와 5의 개수 중에서 더 개수가 작은 값이 팩토리얼 0의 개수였습니다. 그래서 5로 나눠질 때와 2로 나눠질 때를 나누어서 풀었습니다. 그래서 그 둘 중
개수가 더 작은 값을 출력하였습니다.