백준 2004 : 조합 0의 개수(파이썬)

 

---

코드

#https://teching.tistory.com/
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
def countTF(num, d):
    cnt = 0
    div = d
    while div <= num:
        cnt += num//div
        div *= d
    return cnt

print(min(countTF(n,2)-countTF(k,2)-countTF(n-k,2),
          countTF(n,5)-countTF(k,5)-countTF(n-k,5)))

해설

https://teching.tistory.com/110

백준 1676 : 팩토리얼 0의 개수 (파이썬)

위 문제를 응용한 문제이다.

따라서 위 문제를 먼저 풀어서 0의 개수를 세는 방법에 대해서 익히는 것이 좋다.

(이 문제에서는 따로 설명하지 않도록 하겠다.)

이항 계수는  n, k가 주어졌을 때 n!/k!(n-k)! (0<=k<=n)의 식을 만족한다.

따라서 팩토리얼 나누기 팩토리얼 형태가 나온다.

또한 곱셈은 2, 5각각 개수를 더 해주면 되고 ( 10 * 10 = 100)

나눗셈은 2, 5각각 개수를 빼 주면 된다. ( 10/ 10 = 1)

 

또한 이전 문제에서는 5의 개수만 확인하면 됐었지만 나눗셈이 있기 때문에 소인수분해했을 때 2의 개수가 5의 개수보다 적어질 가능성이 있으므로 2의 개수와 5의 개수 전부다 확인을 해주어야 한다.