BOJ 1676번 팩토리얼 0의 개수

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1676/1676/%EC%86%8C%EC%8A%A4.cpp

 

처음엔 대체 어떻게 푸는걸까

계란을 까먹으면서 곰곰히 생각해보았다.

500!을 어떻게 알지?.. 그래서 0을 만들 수 있는 조건이 뭐가 있을까 생각해봤다.

공책에 끄적여보니 0-4 : 0개, 5-9 : 1개, 10-14 : 2개, 15-19 : 3개 20 : 4개 이렇게 나오길래

아 이건 5를 나눈 몫이 답이겠구나 하고 제출했다.

틀렸다.

왜일까 다시 생각해보니 5로 의해 만들어진다면 5의 곱들에 의해서도 만들어질수 있을 것 같았다.

그래서 500 이하의 5 제곱수인 25, 125 를 추가해서 제출했다. 

 

#include <iostream>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    cout << N / 5 + N/25 + N/125;
    return 0;
}