1676번 팩토리얼 0의 개수 with C++

문제

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

1676번: 팩토리얼 0의 개수

 

해결한 방법

n에서 1씩 줄여가며 각 숫자에 2와 5의 개수를 세어서 둘 중 작은 수를 출력해주었습니다.

#include <iostream>
using namespace std;

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

	int n;
	cin >> n;

	int two = 0, five = 0;
	int temp;
	while (n) {
		temp = n;
		while (!(temp % 2)) {
			temp /= 2;
			two++;
		}

		while (!(temp % 5)) {
			temp /= 5;
			five++;
		}
		
		n--;
	}

	if (two < five)
		cout << two;
	else
		cout << five;
	
	return 0;
}

개선한 방법

결과에서 5의 몇 승인지만 세면 되고 n이 500이하라는 제한이 있어서 5, 25, 125로 나눈 몫을 더한 값이 정답임을 알 수 있습니다.

ex) 20까지 5의 배수 개수는 4개 따라서 ans = 4

73까지 5의 배수는 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70 총 14개 이중 25의 배수 하나당 1씩 더하면 ans = 16

#include <iostream>
using namespace std;

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

	int n;
	cin >> n;

	cout << n/5 + n/25 + n/125;
	
	return 0;
}