백준 알고리즘. 팩토리얼 0개 개수 풀이 및 해설

n팩토리얼은 1부터 n까지의 곱을 의미하지요.

​

예를 들면 10팩토리얼은 1x2x3x4x5x6x7x8x9x10 입니다.

10팩토리얼의 값은 얼마일까요? 3628800 입니다.

그렇다면 20팩토리얼의 값은 얼마일까요? 2432902008176640000 입니다.

컴퓨터가 얼마나 빠른지 이 숫자를 0.001초 이내에 계산합니다. 엄청나지요.

​

그렇지만 컴퓨터는 계산할 수 있는 자릿수 제한이 있어서

무한정 계산을 할 수 있는 것은 아니고 그 자릿수 이내에서만 계산이 가능합니다.

​

만약 500팩토리얼을 계산한다면 1x2x3x4x...x500

어마어마한 숫자가 됩니다.

10팩토리얼은 뒤에 붙는 0의 갯수만 2개이고 ( 3628800 )

20팩토리얼은 뒤에 붙는 0의 갯수가 4개이지만, ( 2432902008176640000 )

500팩토리얼은 뒤에 붙는 0의 갯수만 무려 124개입니다.

​

하지만 컴퓨터는 이런 어마어마한 숫자는 계산할 수 없습니다.

( 기본 연산이 아닌 별도의 프로그램을 개발한다면 가능할듯 하지만요 :) )

​

이번 백준 문제는 최대 0 ~ 500팩토리얼까지의 숫자가 주어질때,

뒤에 따라오는 0의 갯수를 알아내는 것입니다.

​

문제 링크는 아래와 같습니다.

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

​

크레이의 해설

0의 갯수를 어떻게 구할 수 있을까요?

의외로 간단한 방법으로 알 수 있습니다.

​

1부터 500까지 곱해 나갈때

0이 언제 1개씩 생기는지를 조사해서, 그 갯수를 하나씩 세면 되는 것이지요 :)

​

우선 10이 곱해질때 0이 하나 생겨납니다.

100이 곱해질 때는 0이 두개 생겨나구요.

그렇다면 10의 배수, 100의 배수일 때 하나씩 생겨나는 거군요?

그렇게 생각하면 정답이 아닙니다.

​

1부터 5까지 곱해볼까요?

1x2x3x4x5 = 120

엇, 10을 곱한 적이 없는데 0이 하나 따라붙었군요.

그것은 바로 2x5가 10이기 때문입니다.

​

즉, 곱하는 모든 수에서 2x5로 표현할 수 있는,

그러니까 2의 배수와 5의 배수를 모두 세면 됩니다.

그리고 작은 갯수만큼 0이 붙는다 생각하시면 됩니다.

​

하지만 2의 배수는 짝수이기 때문에 5의 배수보다 무조건 갯수가 많습니다.

결국 5의 배수의 갯수만 세면 되는 것이지요.

​

하지만 이 때도 한가지 더 감안해야 할 부분이 있습니다.

25를 곱한다고 쳐볼까요?

25 는 5x5 입니다. 5를 2번 사용하지요.

그러니가 앞에 충분히 많은 2가 있기 때문에 2x5 가 2번 발생한다고 보시면 됩니다.

즉 25의 배수는 0이 2개 붙는 경우가 됩니다.

125도 특별한 숫자인데 살펴볼까요? 125 는 5x5x5 로 표현할 수 있는데요.

이 경우에도 충분히 많은 2가 앞에서 나왔기 때문에 2x5, 2x5, 2x5의 계산식으로 표현할 수 있습니다. 결국 125의 배수는 0이 3개 붙습니다.

​

정리해볼까요?

0이 붙는 경우는

​

5의 배수를 곱하면 0이 1개 붙음

25(5x5)의 배수를 곱하면 0이 2개 붙음

125(5x5x5)의 배수를 곱하면 0이 3개 붙음

​

625(5x5x5x5)의 배수를 곱하면 0이 4개 붙습니다면

백준 알고리즘 문제에서는 500까지만 숫자를 제한하였기에 이 경우는 제외하였습니다.

​

본 문제의 범위는 아니지만, 10000팩토리얼에 붙는 0의 갯수를 돌려봤는데 2495개더라구요 :)

​

소스

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <list>
using namespace std;

void Result()
{
	int n;
	scanf("%d", &n);	// 문서갯수, 궁금한 위치

    // 0팩토리얼 예외 처리
	if(n==0)
	{
		printf("0\n");
		exit(0);
	}
	// 5의 배수일 경우 0이 한개씩 발생
	// 25의 배수일 경우 0이 한개 더 발생
	// 125의 배수일 경우 0이 한개 더 발생
	int count_0=0;
	for(long i=2;i<=n;++i){
		if(i%5==0)count_0++;
		if(i%25==0)count_0++;
		if(i%125==0)count_0++;
	}
	printf("%d\n", count_0);
}

int main()
{
	Result();
	return 0;
}