팩토리얼

팩토리얼은 1부터 그 수보다 작거나 같은 수를 모두 곱한 값이다

예를 들어 5의 팩토리얼은 5! 라 표시하고 1 * 2 * 3* 4* 5 해서 120이 된다.

 

즉 팩토리얼은 매우 큰 값이 나오게 되어 있어서

팩토리얼 자체를 구하는 문제보단 팩토리얼 값에 있는 0의 갯수를 정하는 식의 문제가 나온다.

 

근데 물론 팩토리얼 값을 구하고 거기서 0의 갯수를 새는 건 의미가 없으니

다음과 같은 방법을 사용할 수 있다

 

팩토리얼 값을 소인수 분해해봤을 때 0이 나오는 건 10 

그러니까 2와 5를 곱했을 경우에만 가능하기 때문에 

소인수 분해했을 때 나오는 5의 갯수가 곧 팩토리얼 값의 0의 갯수와 같다.

 

이걸 구현할 때는 물론 팩토리얼 값을 구해서 소인수분해를 직접해보는 건

이렇게 값을 우회해서 구하는 의미가 없는 일이고

팩토리얼 N의 값을 5로 나눠주면 이를 구할 수 있다.

 

다만 이 때 N의 값이 5의 제곱수보다 크다면 이를 반복해줘야 한다.

5의 제곱수는 ( ex 25, 125, 625 ... ) 5가 2번, 3번 4번 들어가는 값이기 때문

 

코드로 구현하면 아래와 같다

 

백준 1676번 팩토리얼 0의 개수 문제 풀이 ( Java )