[백준/Python]2004.조합 0의 개수

 

 

 

해설:

 

단순하게 math 라이브러리에서 factorial 써서 풀었다간

 

m과 n에서 20억 들어와 버리면 시간 초과로 아웃됨.

 

관건은 끝자리가 0이 되려면 저 계산값이 10의 몇 제곱인지를 알아야 함.

 

더 자세히 말하자면 2*5의 몇 제곱인지 알면 됨.

 

그렇담 몇 제곱인지 어떻게 세느냐.

 

우선 2의 배수에는 2가 하나씩 있을거 아님?

 

예를 들어

 

8! 에서 2의 배수는 2,4,6,8 총 4개니까

 

2의 4 제곱이 일단 확보된 거고

 

4의 배수는 4,8 총 2개니까

 

2의 2 제곱이 확보된 거임.

 

8의 배수는 8 총 1개니까

 

2의 1 제곱이 확보됨.

 

총 더해보면

 

2^(4+2+1)이 8! 을 구성하고 있다고 보면 돼!

 

5의 배수도 예를 들어볼까?

 

100! 가 5의 몇 제곱인지 알아보자.

 

5의 배수는 5,10,15,,,100까지 20개

 

25의 배수는 25,50,75,100 총 4개

 

따라서 100! 은 5^(20+4)로 구성되어있음!!!

 

 

import sys
from math import factorial
 
 
def find(N):
    two_cnt = 0
    i = 2
    while True:
        if N // i < 1:
            break
        two_cnt += N // i
        i *= 2
    five_cnt = 0
    i = 5
    while True:
        if N // i < 1:
            break
        five_cnt += N // i
        i *= 5
    return two_cnt, five_cnt
 
 
n, m = list(map(int, sys.stdin.readline().split()))
a, b = find(n)
c, d = find(m)
e, f = find(n - m)
if a - c - e > b - d - f:
    print(b - d - f)
else:
    print(a - c - e)
 

 

위에서 계산한 방식으로

 

n, m, n-m

 

3가지의 경우 각각 계산해주고

 

n! / m! * (n-m)! 이니까

 

지수 간에 덧셈, 뺄셈 적절히 해주면 답이 나온다