[C++][백준 3474] 교수가 된 현우

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

 

풀이

오른쪽 끝에 나오는 0의 개수는 10이 얼마나 곱해졌는가를 구하면 된다

그렇다면 10이 얼마나 곱해졌는가는 2와 5가 몇 개 곱해졌는가를 구하면 된다

이때 2가 곱해진 횟수와 5가 곱해진 횟수 중 더 작은 횟수가 10이 곱해진 횟수라고 보면 되는데, 2는 모든 짝수가 해당되므로 팩토리얼 연산에서는 무조건 5가 곱해진 횟수보다 많다

 

따라서 5가 곱해진 횟수를 세면 되는데, N!을 계산하기 위해 1부터 N까지 루프문을 돌며 5가 등장하는 횟수를 세면 시간초과가 된다(N의 최댓값이 10억이기 때문)

 

N이 125라면, 1부터 125까지를 곱해주어야 한다. 1부터 125까지의 수 중에 5의 배수가 등장하는 횟수는 125를 5로 나누어 쉽게 구할 수 있다

 

그런데 이때 그냥 5로 나눠버리면 25, 125 등 5가 2개 이상 곱해진 경우도 한 개로만 카운트되기 때문에 5^2가 등장하는 횟수(N / 5^2), 5^3이 등장하는 횟수(N / 5^3) ... 까지 구해서 더해주면 총 5가 몇 번 나왔는지를 구할 수 있다

 

제출 코드

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t, n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        int cnt = 0;
        for (int num = 5; num <= n; num *= 5)
            cnt += n / num;
        
        cout << cnt << '\n';
    }
}

 

비슷한 문제

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