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

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

뒤에서부터 0이 아닌 숫자가 나올 때까지 0의 갯수를 구하는 것이다. 0이 나오는 것은 10이 곱해져있다는 것이므로 그 약수인 2와 5가 몇번 곱해지 알면 풀  수 있다.

 

#include <cstdio>

int d[501][2]; // 0 -> 2의개수 1 -> 5의 개수

int aa(int n, int mod) {
    int i = 0;
    while (n % mod == 0) { i++; n = n/mod;}
    return i;
}

inline int minmin(int a, int b) {
    return a < b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 2; i <= n; i++) {
        d[i][0] = aa(i, 2) + d[i-1][0];
        d[i][1] = aa(i, 5) + d[i-1][1];
    }
    printf("%d\n" , minmin(d[n][0], d[n][1]));
}