[BOJ] 1676 팩토리얼 0의 개수

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

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

2^a x 5^b=10^min(a,b)

 

---------------------------------------------------풀이----------------------------------------------------

 

2*5=10이므로, N!에 곱해진 2의 개수와 5의 개수 중 작은 수 만큼 0이 들어갈 것이다.

따라서, 2부터 N까지의 수에 대해 2승의 개수, 5승의 개수를 각각 구해

그 개수 중 작은 것을 출력한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;

// N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수=?
int main(void){
    FASTIO;
    int N;
    cin >> N;

    int two = 0, five = 0;

    // 2와 5의 몇승인지 구하기
    for(int i = 2; i <= N; i++){
        int tmp = i;
        while(tmp % 2 == 0){
            two++;
            tmp /= 2;
        }
        tmp = i;
        while(tmp % 5 == 0){
            five++;
            tmp /= 5;
        }
    }

    // 2의 배수와 5의 배수의 개수 중 작은것.
    if(two < five){
        cout << two << "\n";
    }
    else{
        cout << five << "\n";
    }

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

N이 500까지로 작은 수라 각 수에 대해 2와 5의 몇 승인지 일일이 구해도 문제 없었다.