[백준/2004] 조합 0의 개수 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

def t_count(x):
    ans = 0
    while x != 0:
        x //= 2
        ans += x
    return ans

def f_count(x):
    ans = 0
    while x != 0:
        x //= 5
        ans += x
    return ans

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

print(min(t_count(n) - t_count(n - m) - t_count(m), f_count(n) - f_count(n-m) - f_count(m)))

---

✔ 설명

입력 값이 최대 2억까지 들어올 수 있기 때문에 팩토리얼로 문제를 풀게되면 시간초과가 날 수 있다.

끝자리가 0이 나올려면 2x5 쌍이 필요하기 때문에 2,5 지수 중 작은 값을 구하면 된다.

더 작은 값을 고르는 이유는 2나 5의 배수가 더 있을 수 있기 때문이다. (10이 되려면 2,5 둘 다 필요하지만 12, 14나 25, 75인 경우도 지수는 ++ 되기 때문에 작은 값을 고른다)

즉, nCr 공식을 사용해 n!에서의 2와 5의 개수를 세고, (n-r)!과 r!의 2,5의 지수의 총합을 빼서 둘 중에 더 작은 것을 선택하면 된다.

더 자세한 설명은 참고한 블로그를 확인해주면 될 것 같다.

 

참고 블로그:

https://insight-bgh.tistory.com/337

[BAEKJOON] 2004번: 조합 0의 개수 (Java)

---

✔ 후기

문제 읽다가 이건 factorial로 안풀릴거다라고 생각은 들었는데 그럼 어떻게 풀어야하는지 벙쪄있었다.

구글링을 참고해 풀긴 했지만 처음에는 글을 읽으면서 뭔 소린가 했다 (つ﹏<｡ )

이렇게 이항 계수가 팩토리얼 문제가 나왔는데 입력 값이 큰 경우엔 2x5의 지수 개수로도 풀 수 있는 걸 배울 수 있었다.