팩토리얼 0의 개수

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	54139	26073	21530	47.908%

문제

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

입력

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

출력

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

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

출처

• 데이터를 추가한 사람: 111111111111, his130
• 문제를 만든 사람: author6

알고리즘 분류

• 수학
• 임의 정밀도 / 큰 수 연산

---

5!을 생각해보자

5! = 5 x 4 x 3 x 2 x 1 =120 이다

뒷자리에 0이 생기는 경우는 2와 5가 포함되었을 때 뿐이다.

그럼 해당 팩토리얼에 2와 5가 몇 번 들어가 있는지 확인하면 답을 구할 수 있다.

통과된 코드

#include <iostream>

using namespace std;

int N, temp;
int arr[2];

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++) {
		temp = i;
		while (temp % 2 == 0) {
			arr[0]++; // 0은 2
			temp = temp / 2;
		}

		while (temp % 5 == 0) {
			arr[1]++; // 1 은 5
			temp = temp / 5;
		}
	}

	cout << min(arr[0], arr[1]);

	return 0;
}