팩토리얼 0의 갯수

이는 규칙을 찾아내면, 쉽게 표현할 수 있다.

뒷자리가 0이 나오는 경우는 2와 5가 곱해질 때이다.

즉, 소인수분해 한 뒤 2와 5가 존재할 경우 뒷자리는 0으로 끝난다는 의미이다.

실제 팩토리얼 값을 나열하면 다음과 같다.

이를 보면, 5의 배수마다 0의 카운트 값이 증가하는 것을 알 수 있다.
예외로 25일 경우에는 카운트가 1이 아니라 2가 증가한다.

❓왜일까

위의 표를 보면, 0의 count 갯수는 5의 갯수에 따라 변하는 것을 알 수 있다. 그리고 5의 n승에 따라 카운트 값을 더 추가하도록 구현해준다.

즉, 반복문을 통해 해당 누적합을 추가로 계산해줘야 한다.

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

구현 코드

int count = 0;

while(N >= 5){

	count += num / 5;
    
    num /= 5;

}

이번 개념은 수학 문제에서 너무 큰 값이 예상되는 경우, 어떠한 규칙이 있는지 유무를 확인해볼 필요가 있다는 것을 깨달을 수 있다.

참고 포스팅

[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]