백준 2004번 (큰 숫자의 0 세기)

(n m)은 n!/{k!(n-k)!}이다.

 

처음에는 10이 2와 5를 곱한 값임을 이용해 하나씩 반복문으로 돌리며 (n m)에 2와 5가 몇개 들어있는지 파악해보았다.

하지만 시간초과가 나서 n>=m이므로 n!/m!을 m+1부터 n까지의 수를 모두 곱한 값으로 만들어 다시 짜봤다.

또 시간초과가 났다. 아무래도 n과 m에 큰 수가 들어올 수 있어서 반복문으로는 안될 것 같다.

 

아예 새로운 방법을 공부했다. 예를 들어 25!에 있는 2의 개수를 셀 때 25를 2로 나누어 몫(12)을 모두 변수 two에 담는다.

이 행동의 의미는 2, 4, 6, ---, 24를 한 번씩 센 것이다.

 

다시 이것을 2로 나누어 몫(6)을 two에 담는다.

이 행동의 의미는 4, 8, 12, ---, 24를 센 것이다.

 

또 2로 나누어 몫(3)을 two에 담는다.

이 행동의 의미는 8, 16, 24를 센 것이다.

 

또 2로 나누어 몫(1)을 two에 담는다.

16을 센 것이다.

 

16에는 2가 4개 들어있으므로 총 4번 세진다. 이제 좀 알겠다.