[Algorithm] Baekjoon 1676번 : 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int count = 0;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        if (i % 125 == 0)
        {
            count += 3;
            continue;
        }
        if (i % 25 == 0)
        {
            count += 2;
            continue;
        }
        if (i % 5 == 0)
        {
            count += 1;
        }
    }
 
    cout << count;
 
    return 0;
}

어떠한 수의 끝자리에 점점 0이 추가되려면 2*5가 최소 1번은 들어가있는 수를 곱해야한다는 성질을 이용한 문제다.

즉 2와 5가 몇번들어갔는지 카운팅하면 되는것인데, 2는 짝수의 최소수로서 팩토리얼을 계산하는 과정에서 무수히 많이 들어가 있다. 그렇기 때문에 5의 개수만 카운팅하면 되며, n이 최대 500까지이니 5의 3제곱인 125까지 한꺼번에 체크를 한다.

특정 수 i가 125로 나뉘어 떨어진다는 것은, 5가 3번 곱해져있는 수라는 뜻이니 결국 해당 수를 곱하면 0이 3개가 추가된다는걸 의미한다. 그렇기 때문에 3을 카운팅한다.

25는 제곱이니까 두번, 5는 한번... 

 

팩토리얼문제는 n이 조금만 커져도 자료형범위를 벗어나기 쉽상이니 조심해야한다.