[백준] 1676번: 팩토리얼 0의 개수 - C++

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

첫째 줄에 구한 0의 개수를 출력한다.

---

N!을 구한 다음 10으로 나누어 구하는 방식으로 풀면 N에 500을 대입하였을 때 값이 안나오는 것을 확인할 수 있다.

즉, 팩토리얼의 값을 계산하는 방식으로 풀면 안된다는 뜻이다.

 

뒤에 0이 나온다는 의미는 10의 배수라는 뜻이고, 0의 개수를 구한다는 것은 10의 몇 제곱인지, 곧 팩토리얼이 계산되는 동안 2와 5가 얼마나 들어갔는지를 의미한다.

 

곱해주는 수에 2와 5가 각각 몇개 곱해지는지 센 후 더 적은 값이 답이 되는데, 범위 내에서 5가 더 적게 들어가기 때문에 2의 경우는 계산하지 않았다.

 

코드

#include <cstdio>

int main(void) {
    int n;
    scanf("%d", &n);

    int count = 0;
    
    for(int i = 5; i <= n; i *= 5) {
        count += n / i;
    }
    printf("%d\n", count);
    return 0;
}