[Python] 백준 2004번 - 조합 0의 개수(실버2)

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

2004번: 조합 0의 개수

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 수학
 - 정수론

문제

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

입력

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

출력

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

---

처음엔 단순히 팩토리얼로 해봤는데 20억의 숫자는 당연히 불가능했다.

 

팩토리얼이 아닌 다른 방식으로 풀어야 함을 금방 깨달았다.

 

이내 발견한 방법이

5와 0의 개수만큼 0의 개수가 추가되며 5의 제곱수만큼이 또 더해진다는 것을 알게 되었다.

 

5! = 1개

10! = 2개

15! = 3개

...

25! = 6개 ($5^2%)

50! = 12개

75! = 18개

 

그래서 처음엔

import sys
input = sys.stdin.readline
import math

n, m = map(int, input().split())

def div(value):
    total = 0
    five = 5
    i = 1
    while five <= value:
        total += value // five
        i += 1
        five = 5**i
    return total

a = div(n)
b = div(n-m)
c = div(m)

print(a-b-c)

위와 같이 풀었다.

 

각 0의 개수를 구해서 빼주면 되는것이엇다.

 

하지만 틀렸다.

 

그래서 질문게시판의 반례를 보다가 '5 1'이 입력되면 0이라는 것을 알게 되었다.

 

즉 5의 개수만 세는 것이 아닌 2의 개수도 같이 세주어 더 작은 수의 개수로 출력하는 문제였던 것이다.

 

import sys
input = sys.stdin.readline
import math

n, m = map(int, input().split())

def div_five(value):
    total = 0
    five = 5
    i = 1
    while five <= value:
        total += value // five
        i += 1
        five = 5**i
    return total

def div_two(value):
    total = 0
    two = 2
    i = 1
    while two <= value:
        total += value // two
        i += 1
        two = 2**i
    return total

a = div_five(n)
b = div_five(n-m)
c = div_five(m)

d = div_two(n)
e = div_two(n-m)
f = div_two(m)

print(min(a-b-c, d-e-f))

어려운 문제였다... 실버 2문제에서 계속해서 너무 헤매게 된다.