[백준] 팩토리얼 0의 개수 (C++)

Key

N은 최대 500이고, 500!을 감당할 수 있는 자료형이 없다. 따라서 직접 팩토리얼 수를 계산하는 방식을 사용할 수 없다.

0의 하나면 10의 배수라는 뜻이다. 10은 2*5이다. 100은 2*2*5*5이다. 즉, 0의 개수는 2와 5 쌍의 개수와 같다는걸 알 수 있다. 

 

10!을 예로 들면, 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 이다. 여기서 2의 배수는 총 5개, 5의 배수는 총 2개. 따라서 결과값 뒤에는 00이 붙어있을 것이다. 계산기로 계산해보면 3628800이므로 0 두개가 맞다.

 

 

Idea

N을 이루고 있는 2와 5쌍 개수를 세야하는데, 이 때 5의 배수가 몇개인지만 고려하면 된다. 왜냐하면 2는 모든 짝수에 포함되기 때문에 어떤 수라도 무조건 2는 5보다 개수가 많거나 같다는게 보장된다.

 

5의 개수를 세는 법은 다음과 같다.

 

 

• 5의 배수는 5, 10, 15, 20, 25, ...이다. 여기서 5의 배수는 하나의 5를 포함한다.
• 25의 배수는 25, 50, 75, 100, ...이다. 여기서 25는 두 개의 5를 포함한다.
• 125의 배수는 125, 250, 375, ...이다. 여기서 125는 세 개의 5를 포함한다.

 

 

따라서 N을 5의 거듭제곱으로 나눠주면 2와 5가 몇 쌍있는지, 즉 0의 개수를 셀 수 있다.

 

 

Code

#include <iostream>
#include <string>
using namespace std;

int countZero(int n) {
	int cnt = 0;

	for (int i = 5; n / i>=1; i *= 5) {
		cnt += n / i;
	}
	return cnt;
}

int main() {

	int N = 0;

	cin >> N;

	cout << countZero(N) << "\n";

	return 0;
}

 

 

회고

난이도가 낮게 책정되어있어서 처음엔 생각없이 팩토리얼 수를 직접 계산해서 string으로 바꾸고 뒤에서부터 0 개수를 셌다. 당연히 틀렸고 다른 방법을 생각했는데 1차원적인 방법만 생각나고 제대로 수 크기를 줄일 방법을 생각하지 못했다. 결국 도움을 받아 풀었는데 10은 2와 5의 곱이고 따라서 5배수 개수만 세면 된다는 사실을 발견했을때 너무 획기적인 생각이라 깜짝 놀랐다. 조금 더 생각을 넓히는 연습을 하자!