본문 바로가기
코딩과 알고리즘

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

728x90

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;
}

 

728x90
반응형