[BOJ][⚪2][백준#02004] 조합 0의 개수

문제 출처

BAEKJOON Online Judge #2004

문제

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

입력

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

출력

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

예제

입력

25 12

출력

2

My Sol

def calc_tf(n):
    def calc_k(n, k):
        cnt = 0
        while n:
            cnt += n // k
            n = n // k
        return cnt

    return calc_k(n, 2), calc_k(n, 5)

n, a = map(int, input().split())
b = n - a

n2, n5 = calc_tf(n)
a2, a5 = calc_tf(a)
b2, b5 = calc_tf(b)
r2 = n2 - a2 - b2
r5 = n5 - a5 - b5
print(min(r2, r5))

팩토리얼을 계산해보면 되는데, k로 나눈 몫을 cnt에 더하고 n을 n//k로 취한다. 이렇게 n이 0이 될 때까지 반복하면 해당 n! 내의 k의 곱을 구할 수 있다.

이것을 n, a, b에 각각 취해서 값을 구하고, a, b의 2, 5의 곱 개수를 더해 n의 2, 5의 곱 개수에서 빼준다. 이것이 n!/(a!*b!)에서의 2와 5의 곱의 개수이다. 10은 이 두 개의 수 중 작은 수만큼 곱해져있다. 이를 min 함수로 계산하여 출력한다.

결과

맞았습니다!!

모범답안

출처

def zero(n:int, m:int, x:int)->int:
  ret=0
  temp=x
  while n>=temp:
    ret+=n//temp-(n-m)//temp-m//temp
    temp*=x
  return ret
  
n,m=map(int,input().split())
n2=zero(n,m,2)
n5=zero(n,m,5)
print(min(n2,n5))

풀이과정이 굉장히 짧은 분의 코드를 분석해보려 한다. 수식 자체는 굉장히 복잡한데, 나눠지는 수를 낮춰주는 것이 아니라 나누는 수를 높이면서 반복을 진행하는 방식을 사용했다. 그리고 수마다 하는 것이 아니라 전체 과정의 2와 5의 곱의 개수를 구했다.

특이한 풀이이고, 깔끔하게 풀었지만 내가 이렇게 풀라고 해도 못 풀 것 같다ㅋㅋ