BOJ 2004 : 조합 0의 개수

입력

문제 자체를 이해 못해서, 풀지 못 하고 답안을 보고 해설을 참고한다. https://changsroad.tistory.com/95

[Python] 백준 #2004- 조합 0의 개수

여러 해설들을 봤지만, 이게 가장 잘 상술 되어있었다.

요약하면,

조합(Combination)의 수식은 팩토리얼의 조합인 https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

조합 - 위키백과, 우리 모두의 백과사전

조합 수식.

위와 같이 정의할 수 있고, 이때 문제에서 정의하는 0이라는 값은 10의 배수일 때만 생성 될 수 있다. 그리고 10은 5와 2의 최소의 곱으로 이루어져 생성된다. 또한, 문제에서 끝자리의 0의 개수이므로, 최소한의 5의 개수와, 2의 개수를 곱하면 0의 개수가 나온다.

그럼, 문제를 푸는 방법을 구해보자. 먼저 각 팩토리얼에서 5의 개수를 찾아주어야 한다. 이는 팩토리얼을 5로 나눈 몫(정수로 떨어지는)과 같고(25 = 5 * 5 : 2개, 20 = 5 * 4 : 1개,... 5*1 : 1개, 즉 25!는 6개가 된다.) 이는 전체 팩토리얼의 수를  나눠서 떨어지는 개수를 구하는 것과 같다. 그런데 이걸 위에 팩토리얼에서 밑에 팩토리얼 값들로 나눈것을 계산하는 것이므로, 지수의 '빼기'가 이루어진다. 다음 참조. https://somjang.tistory.com/entry/BaeKJoon-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98-Python

[BaeKJoon] 2004번: 조합 0의 개수 (Python)

그러면, 분자 개수에서 분모 개수들을 빼주게 되면 조합(Combination)의 최종 0자리 개수가 구해진다. 이를 10의 나머지 약수인 2로도 테스트 했을 때, 가장 작은 수를 선택하면 정답이 된다.