28. N!에서 0의 개수

it 취업을 위한 알고리즘 문제풀이

문제

코드1

코드2

문제해결방법

• factorial을 직접 구하고 10의 배수를 구하면 long long의 범위 마저 넘는 수 생기므로
• 계산하지말고 소인수 분해를 한다.
• 소인수분해 하는 방법은 1부터 n까지 2로 나누어 떨어지지 않을 때까지 나누고 나누어 떨어지지 않으면 3으로 나누고 다시 3으로 나누어 떨어지지 않으면 4로 나누는데 이때 4로는 절대 나누어 떨어지지 않으므로 걱정하지 않아도 된다. 이유는 이미 2로 나누어 떨어지지 않을 때까지 나누었기 때문에 2의 배수로는 앞으로도 나누어 떨어지지 않는다. 이렇게 2,3,4,5... 나누어떨어질때 까지 나누고 체크배열에 인덱스값과 해싱기법에 따라 개수를 표시한다.
• 반복문에서 5와 2의 개수를 and조건에 따라 개수를 카운트 한다. 카운트 후에는 다음 카운트에 계산되지 않기위해 제외해준다.
• 코드 2는 위와 거의 같지만 소인수 분해를 하면서 2의 개수와 5의 개수만 미리 카운트해서 다시 반복문을 한번더 체크하는 연산회수를 줄인다. 그리고 2와 5가 짝이 맞아야 10의 배수가 되므로 작은 값을 출력하게 한다.