[백준 2004] 조합 0의 개수

 

조합 nCm의 값 중 끝에 오는 0의 개수를 구하는 문제이다

nCm = n! / (n-m)!*m! 공식을 사용하여 팩토리얼을 계산하고 0의 개수를 세어줄 수 있겠지만 정수 n,m의 범위를 보았을 때 시간 초과가 날 것을 고려하여 소인수분해를 사용하였다

 

nCm을 소인수분해 하였을 때 2와 5가 한 쌍이 되어 하나의 0이 만들어지기에(2*5 = 10) 5의 개수가 더 작을 것이라 생각하고 5의 개수를 구하였다

5 = 5

25 = 5*5

125 = 5*5*5

와 같은 패턴을 적용하여 소인수분해 하고자 하는 limit내의 지수 5의 개수를 구하였다

제출 결과는 틀렸으며 지수 2의 개수가 5의 개수보다 적은 경우도 존재한다는 것을 알았다

 

지수 2와 5의 개수를 모두 구하기 위해 함수를 만들고

def CountZero(limit,repeat):
    zero = 0
    i=repeat
    while(limit >= i):
        zero += limit//i
        i *= repeat
    return zero

 

 

repeat에 2와 5를 대입하여 반환되는 개수들을 n! / (n-m)!*m!에 대입하였다

two = CountZero(nm[0],2)-CountZero(nm[0]-nm[1],2)-CountZero(nm[1],2)
five = CountZero(nm[0],5)-CountZero(nm[0]-nm[1],5)-CountZero(nm[1],5)

print(min(two,five))

 

2와 5의 개수 중 더 적은 변수를 출력하여 마무리했다