📚 2004 - 조합 0의 개수

조합 0의 개수

풀이

• 조합식 : nCr = n! / (n-m)!r!
• 끝자리 0의 개수를 출력한다.

조합식을 보면

• 분모에는 : n!
• 분자에는 : (n-m)!, r!

가 있다.

➡ 그러므로 0의 개수는 분자에 있는 0의 개수에서 분모에 있는 0의 개수를 빼주면 된다. (100/10 => 10)

또한, 10의 배수는 2와 5의 배수이다. (두 수 개수가 같다면 10의 배수가 된다.)
➡️ 분자에 있는 0의 개수에서 분모에 있는 0의 개수를 빼줄 때 2와 5로 각각 구한 후, 두 수로 나온 결과에서 작은 값이 0의 개수(10의 배수)가 된다.

소스

from sys import stdin as s

n, m = map(int, s.readline().split())


def comb(cur_data, div):
    cnt = 0
    while cur_data:
        cur_data //= div
        cnt += cur_data

    return cnt


two_data = comb(n, 2) - comb(m, 2) - comb((n - m), 2)
five_data = comb(n, 5) - comb(m, 5) - comb((n - m), 5)

print(min(two_data, five_data))

실행 결과