1676번: 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

문제를 너무 간단하게 생각했다. 팩토리얼 구한 뒤 0의 갯수를 체크하려 하였는데 당연히 500!같이 큰 수의 경우 시간초과가 났다.

그래서 규칙을 찾아보았다. 접근은 좋았으니 5의 갯수를 세어야 하는데 5로 나눈 몫을 구했다.. 25와 125같은 경우만 처리하면 되는줄 알았는데 50, 75, 100, 등등 너무 많은 수가 있었기에 이것 또한 불가능하였다.

 

잘못된 접근 모음,,

 

결국 문제의 핵심은 2를 몇 번 곱하였고 5를 몇 번 곱하였는지를 계산하여 10을 곱한 횟수를 통해 0의 갯수를 세는 것이다.

하지만 문제를 다 풀고 여러 풀이를 보다 안 사실인데 보통 2의 갯수가 5의 갯수보다 많기에 굳이 2의 갯수를 세어주지 않아도 된다. 따라서 5의 갯수만 세어주면 된다.

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, num5 = 0;
    cin >> n;
    while(n > 0)
    {
        int num1 = n;
        while(num1 % 5 == 0)
        {
            num5++;
            num1 /= 5;
        }
        n--;
    }
    cout << num5;
    return 0;
}