백준 1676번 C++

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

1676번: 팩토리얼 0의 개수

와.. 문제보고 재귀로 팩토리얼 다 만들고 10으로 나누니 시간 초과가 뜬다.

어떻게든 줄어보려고 재귀에 이상한 짓 다 했는데 계속 시간초과가 떠서 뭐가 문제인지 모르겠었다.

근데 2*5가 10이 되는 걸로 푼다는게 아닌가.. 배신감...

 

즉 팩토리얼에 5가 몇번 곱해지는지 보면 된다.

5가 나오면 count+1, 25면 count +2처럼...

계속 생각했는데 생각도 못한 방법이다.

 

#include <iostream>

using namespace std;


int main(){
    int n;
    cin >> n;       //n입력
    int count =0;
    for(int i =5; i<=n; i++){
        int a = i;
        while(a%5 == 0){
            a = a/5;
            count++;
        }
    }
    cout << count;
}