2004 조합 0의 개수

끝자리에 있는 연속된 0의 개수를 찾는 문제다. 0이 나온다는 것은 10이 곱해졌는 얘기고, 10을 소인수분해하면 2, 5의 인수가 나오기 때문에 2, 5 중 최소 개수를 찾으면 된다

 

N 제한이 20억이기 때문에 20억을 모두 탐색하면서 나머지 연산을 할 수는 없다

빠르게 2, 5의 개수를 찾는 방법

[참고] https://ksj14.tistory.com/entry/BackJoon1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98

 

따라서 조합은 nCr = n! / ((n-r)!*r!) 이므로 각 값에 해당하는 2, 5의 개수를 각각 배열에 담아서 저장해서 마지막에 계산하면 된다. 분자와 분모는 -관계이기 때문에 빼주면서 최소값을 찾으면 된다

 

문제: https://www.acmicpc.net/problem/2004

깃허브주소: https://github.com/surinoel/boj/blob/master/2004.cpp