백준 2004번 파이썬 - 조합 0의 개수

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

 

문제

 (𝑛𝑚)$n \choose m$의 끝자리 0$0$의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 𝑛$n$, 𝑚$m$ (0≤𝑚≤𝑛≤2,000,000,000$0 \le m \le n \le 2,000,000,000$, 𝑛≠0$n \ne 0$)이 들어온다.

출력

첫째 줄에 (𝑛𝑚)$n \choose m$의 끝자리 0$0$의 개수를 출력한다.

예제 입력 1 복사

25 12

예제 출력 1 복사

2

 

 

처음 작성한 코드

import sys
input = sys.stdin.readline
a,b = map(int,input().split())
def factorial(n):
  if n ==0:
    return 1
  else:
    return n *factorial(n-1)
ans = int(factorial(a)/factorial(b))
print(ans)
ans2= 0
for i in ans:
  if i == '0':
    ans2 +=1
print(ans2)

이렇게 작성하니  런타임에러(Recursion Error)가 떴다.

이러한 에러가 뜬 이유는 입력 값이 큰 경우 재귀 깊이 제한으로 인해 발생한 것이다. Python에서 기본적으로 설정된 재귀 깊이 제한은 대략 1000 정도이기 때문에, $n$이 큰 경우 이 한계를 초과하여 오류가 발생한다.

 

이런문제에서는 다르게 접근해본다.

끝자리 0의 개수를 구하는 문제에서는 실제로 조합의 값을 계산할 필요가 없다. 끝자리 0의 개수를 구하는 것은 사실상 10의 배수, 즉 2와 5의 소인수의 개수를 세는 것과 동일하다. 

 

1) a,b에 대해 a! b! (a-b)! 에서 각각 2와 5의 소인수의 개수를 센다. (a-b)!  소인수 개수 빼주는 이유는 같은 소인수의 개수를 각각 빼줌으로써, 실제 조합의 결과에 포함되는 해당 소인수의 최종 개수를 구할수 있다. 

2) 센 소인수의 개수를 이용하여 최종적인 2와 5의 소인수의 개수를 찾아낸다.

3) 2와 5의 소인수 중 더 적은 수를 선택하면 그것이 끝자리 0의 개수가 된다.

10은 2와 5의 곱으로 이루어져 있기 때문에, 결과값에서 2와 5가 함께 얼마나 많이 곱해지는지가 끝자리 0의 개수를 결정한다. 예를 들어, 어떤 수에 2가 3번, 5가 2번 곱해진다면, 최종적으로 그 수는 10의 제곱을 한 번과 추가로 2를 한 번 더 곱한 형태가 된다. 이경우 끝자리에 0이 2개가 된다. 그러므로 끝자리 0의 개수를 결정하는 것은 곱해진 2와 5 중 더 적은 수이다. 

 

최종 코드

def count_factors(n,factor):
  count = 0
  while n:
    n //= factor
    count +=n
  return count
import sys
input = sys.stdin.readline
a,b = map(int,input().split())
count_2 = count_factors(a,2) - count_factors(b,2) - count_factors(a-b,2)
count_5 = count_factors(a,5) - count_factors(b,5) - count_factors(a-b,5)
print(min(count_2,count_5))