문제
https://www.acmicpc.net/problem/1676
풀이
sol1) 직접 팩토리얼 계산한 뒤에 0 개수 확인
➡️ 범위 long long으로 해도 오버플로우
sol2) 팩토리얼 계산하며 10으로 나눠지면 나누고, 0 개수 cnt++
➡️ 매번 문자열로 바꿔서 0 있나 봐야하므로 비효율적
sol3) 2와 5의 개수 찾기
💡2보다 항상 5가 적으므로 5 개수만 찾으면 됨
5면 0을 1개 만들 수 있고
25면 0을 2개 만들 수 있고
125면 0을 3개 만들 수 있고
(N이 500이하라서 625는 나올 일 없음)
=> n을 5로 나눈 몫을 더하면 됨
코드
#include <iostream>
using namespace std;
int main() {
int n;
int cnt = 0;
cin >> n;
for (int i = 5; i <= n; i *= 5) {
cnt += (n/i);
}
cout << cnt;
return 0;
}
👩🏻💻