백준 1676: 팩토리얼 0의 개수

문제 요약

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

문제 분류

• 수학

문제 풀이

i = 2부터 n까지, i의 2와 5의 약수의 개수를 구한 뒤, 최솟값을 출력하면 된다.

이때, 2의 약수를 셀 때에 4의 경우는 2개, 8의 경우는 3개로 세야 하므로 i % 2를 구한 후 i /= 2를 해야한다.

5의 약수를 셀 때도 마찬가지. 5, 10, 15는 1개지만, 25는 2개가 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n, two = 0, five = 0, temp;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		temp = i;
		while (!(temp % 2)) {
			two++;
			temp /= 2;
		}
		while (!(temp % 5)) {
			five++;
			temp /= 5;
		}
	}
	cout << min(two, five);
	return 0;
}