[BOJ] 1676번: 팩토리얼 0의 개수

문제 링크

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

접근한 방식

숫자의 뒤에 존재하는 0의 개수는 곧 해당 수를 어떤 수들의 곱으로 나타낼때(단, 10을 만들 수 있으면 무조건 포함시키기) 그중에서 10의 개수를 의미한다.
따라서 10은 2 x 5 이기 때문에 2와 5가 한번씩 나온 횟수를 구하면 된다.

예를들어 10!에서의 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지의 0의 개수를 구한다고하면,
10!
= 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10
= 1 x 2 x 3 x (2 x 2) x 5 x (2 x 3) x 7 x (2 x 2 x 2) x 9 x (2 x 5)
에서
2의 개수가 8개, 5의 개수가 2개이므로
2와 5가 한번씩 카운트되는 횟수는 2회이다.

따라서 위처럼 1부터 n까지 각각의 수에 대해 2와 5의 개수를 카운트하고, 2와 5가 한번씩 카운트되는 횟수(2의 개수와 5의 개수중 작은 값)을 구하면 된다.

코드

<C++>

#include <iostream>
#include <algorithm>
#define endl '\n'

using namespace std;

int N;
int solution(int n) {
	int cnt_2 = 0, cnt_5 = 0; // 2의 개수, 5의 개수
	// 1, 2, ..., n - 1, n에 대한 모든 경우 검사
	for (int i = 1; i <= n; i++) {
		int value = i; 
		// 2 또는 5의 곱셈으로 이루어져있는지 살펴본다.
		while (true) {
			// 2와 5로 모두 나누어 떨어지면
			if (value % 2 == 0 && value % 5 == 0) {
				// 각각의 개수를 증가시키고
				cnt_2++;
				cnt_5++;
				// 10으로 나눔
				value /= 10;
			}
			// 2로만 나누어 떨어지면
			else if (value % 2 == 0) {
				// 2의 개수를 증가시키고
				cnt_2++;
				// 2로 나눔
				value /= 2;
			}
			// 5로만 나누어 떨어지면
			else if (value % 5 == 0) {
				// 5의 개수를 증가시키고
				cnt_5++;
				// 5로 나눔
				value /= 5;
			}
			// 2와 5중 아무것으로도 나누어떨어지지 않는다면 루프 종료
			else
				break;
		}
	}

	return min(cnt_2, cnt_5);
}

int main() {
	cin >> N;

	cout << solution(N) << endl;

	return 0;
}