> [!date] published: 2022-01-31
[1676번: 팩토리얼 0의 개수](https://www.acmicpc.net/problem/1676)
## 🌟 문제
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
## 🌟 입력
첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
## 🌟 출력
첫째 줄에 구한 0의 개수를 출력한다.
## 🌟 풀이
500팩토리얼은 숫자 자료형으로 담기에는 너무 큰 수이기 때문에 절대 팩토리얼을 직접 구해서 0의 개수를 구하는 문제는 아니다.
숫자의 끝에 0이 몇개가 될 지 여부는 이 수를 인수분해했을 때 10이 몇번 곱해져있는지를 확인해보면 알 수 있다.
따라서 1부터 N까지 각각의 수를 곱셈으로 표현했을 때 (즉 인수분해) 2가 곱해지는 횟수와 5가 곱해지는 수를 세서 더 작은 수를 구해주면 그것이 바로 N!에서 뒤에서 처음 0이 아닌 숫자가 나올 때까지의 0의 개수가 될 것이다.
(같은 제목의 더 난이도가 높은 문제도 있다. 일단 이 1676번은 최대 500팩토리얼로 비교적 N의 크기가 작은 편이라 이렇게 일일이 곱해지는 2와 5의 개수를 구해줘서 문제를 풀 수 있었지만 동명의 다른 문제는 N의 최댓값이 100,000,000이기 때문에 같은 방법으로는 풀 수 없을 것 같다. ... 그 다른 문제는 아직 안풀어봤기 때문에 다음에 풀게 되면 여기 추가하겠다.)
## 🌟 코드
```c
/*
2022-1-30
1676_팩토리얼 0의 개수
https://www.acmicpc.net/problem/1676
*/
#include <iostream>
#include <cmath>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int cnt2 = 0, cnt5 = 0;
int N, temp;
cin >> N;
for (int i = 1; i <= N; i++){
temp = i;
while ((temp % 2) == 0){
cnt2++;
temp /= 2;
}
temp = i;
while ((temp % 5) == 0){
cnt5++;
temp /= 5;
}
}
cout << min(cnt2, cnt5);
return (0);
}
```