BOJ 1676번 :: 팩토리얼 0의 개수

#문제

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

1676번: 팩토리얼 0의 개수

 

#작성 코드

#include <iostream>
using namespace std;
 
int n;
int two, five=0;
 
int main(){
    cin>>n;
    
    // 2부터 시작해서 n까지의 수에 2와 5가 인수로 몇 개 존재하는지 센다 
    for(int i=2; i<=n; i++){
        int tmp=i;
        while( tmp%2==0 ){
            tmp = tmp/2;
            two++;
        }
        while( tmp%5==0 ){
            tmp = tmp/5;
            five++;
        }
    }
    
    // 2*5=10
    // 10은 2와 5의 개수 중 더 작은것만큼 만들 수 있다. 
    int result = min(two, five);
    cout<<result<<'\n';
    return 0;
}

##

N!은 1부터 N까지의 곱이다.

-> N!에서 0이 아닌 수가 나올 때까지 등장하는 0의 개수는 N!에 약수로 10이 몇 개 존재하는지 묻는 것이다.

-> 10은 2 * 5이므로 N!에 2와 5가 몇 개 들어있는지 센다.

-> 2부터 N까지의 수를 반복하여 2와 5로 얼마나 나누어떨어지는지 체크하고, 나누어떨어지면 2또는 5 중 해당하는 수의 개수를 하나 늘린다.

2와 5가 a, b개 존재한다면 만들 수 있는 10은 최대 min(a, b)개이다.