[백준/Python]2004_조합 0의 개수

문제

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

2004번: 조합 0의 개수

풀이

단순히 \( _{n}\mathrm{C}_{m} \) 으로 답을 구하기엔 n과 m이 20억일 때 제한시간을 초과할 수 있습니다.(1000만 ~ 10억 개의 연산이 약 1초 소요)

 

따라서 수학적으로 접근해서 풉니다.

 

조건(1): \( _{n}\mathrm{C}_{m} = {_{n}\mathrm{P}_{m} \over m!} = { n! \over m! \times (n - m)!} \)

조건(2): 어떠한 수x가 있을 때, x를 인수분해했을 때 인수 10이 존재할 때마다 x의 뒷자리에 0이 붙습니다.

-> \(10 = 2 \times 5\) 이므로 인자 2와 인자 5가 한 쌍 존재할 때마다 x의 뒷자리에 0이 붙습니다.

 

count_num(k, num) 이라는 함수를 선언합니다. 해당 함수는 k!을 인수분해하여 num 인자의 개수를 구하는 함수입니다.

조건(1)을 이용하여 \( _{n}\mathrm{C}_{m} \) 를 인수분해하여 2 인자의 갯수(two_cnt)와 5 인자의 갯수(five_cnt)를 구합니다. 단, 분모 분자로 소거되는 것은 갯수로 포함하지 않습니다.

min(two_cnt, five_cnt)가 답이 됩니다.

코드

import sys


def count_num(k, num):  # k!를 인수분해했을때 num의 개수를 리턴
    cnt = 0
    while k:
        k = k // num
        cnt += k
    return cnt


n, m = map(int, sys.stdin.readline().rstrip().split())
two_cnt = count_num(n, 2) - count_num(m, 2) - count_num(n - m, 2)
five_cnt = count_num(n, 5) - count_num(m, 5) - count_num(n - m, 5)
print(min(two_cnt, five_cnt))