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

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

 

팩토리얼 연산 후 뒷자리에 0이 있다는 것은 0의 개수만큼의 10을 인수로 가진다는 의미이다. 

10을 다시 소인수분해하면 2x5가 된다.
즉, 팩토리얼에서 모두 소인수분해 한 후 인수 2와 5를 짝지어 개수를 세면 원하는 값을 얻을 수 있다. 

 

이때 팩토리얼에서 인수 2는 항상 인수 5보다 많으므로 인수 5의 개수를 세면 연산 후 뒷자리 0의 개수를 세는것과
같은 효과가 나온다.

따라서 팩토리얼의 숫자들이 5의 배수인지, 배수라면 인수5를 몇개나 가지고 있는 검사하여 그 개수를 출력한다.

 

---

C

더보기

#include <stdio.h>

int countZero(int n){
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int v = i;
        while(v % 5 == 0) {cnt++; v /= 5;}
    }
    return cnt;
}

int main(){
//    int n, m; scanf("%d %d", &n, &m);
    int n; scanf("%d", &n);
    printf("%d", countZero(n));
}

---

Python

더보기

n = int(input())
cnt = 0
for i in range(1, n+1):
    v = i
    while v % 5 == 0: cnt += 1; v /= 5
print(cnt)