[백준] 1676. 팩토리얼 0의 개수

문제

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



풀이

0의 개수는 2 * 5 = 10의 개수를 구하면 되므로 2와 5의 개수를 세어서 2와 5 중 더 적게 있는 것이 답이 된다. 참고로 이 문제는 팩토리얼을 구하면 수가 long long 범위를 초과할 수 있기 때문에 구해서 풀면 안된다.



소스코드

//
//  1676.cpp
//  test
//
//  Created by 신기열 on 27/06/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

long long num[501][2] = { 0, };

int main(){
    
    int n; cin >> n;
    long long num_2 = 0, num_5 = 0;
    
    for(int i = 1; i <= n; i++){
        int j = i;
        while(j % 2 == 0 || j % 5 == 0){
            if(j % 2 == 0){
                num[i][0]++;
                j /= 2;
            }
            if(j % 5 == 0){
                num[i][1]++;
                j /= 5;
            }
        }
        num_2 += num[i][0];
        num_5 += num[i][1];
    }
    
    cout << min(num_2, num_5);
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Else/1676.cpp