백준: 2004 조합 0의 개수

문제

2004번: 조합 0의 개수

 

문제 풀이

 이 문제는 조합의 성질을 이해할 수 있어야 풀 수 있는 문제이다. 조합은 nCm이므로 n! / m! (n - m)!으로 계산 된다.

이때 n!, m!, (n - m)!에 대해 각각 2, 5로 나누어지는지 확인하고 카운트하면 된다. 

 

 그럼 실제 계산을 위해 n! 값들 중에 2, 5의 배수를 찾아야 할까? 아니다. 만약 9인 경우 2의 배수는 2 4 6 8로 4개가 되며, 5의 배수는 5 1개이므로 9 // 2, 9 // 5로 9!에 대한 각 배수들을 찾을 수 있다.

 

코드

def cnt(n, divisor):
    ret = 0
    while n != 0:
        n //= divisor
        ret += n
    return ret

if __name__ == '__main__':
    n, m = map(int, input().split())
    two_cnt = cnt(n, 2) - cnt(m, 2) - cnt(n - m, 2)
    five_cnt = cnt(n, 5) - cnt(m, 5) - cnt(n - m, 5)
    print(min(two_cnt, five_cnt))