백준 2004 - 조합 0의 개수 [파이썬]

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

2004번: 조합 0의 개수

 

풀이 과정

N!에서는 2가 인수로 들어가는 횟수보다 5가 인수로 들어가는 횟수가 항상 더 적었는데 조합에서는 그렇지 않다.

 

 

7C3의 경우 2가 인수로 들어가는 횟수는 0번이고 5가 인수로 들어가는 횟수가 1번임을 알 수 있다.

 

따라서 이번에는 nCk에서 2가 인수로 들어가는 횟수, 5가 인수로 들어가는 횟수를 일일이 세주어야 한다.

 

이므로 number_count(n, k)라는 함수가 n!에서 a가 인수로 몇번 들어가는지 결과값을 반환해준다고 하면

number_count(n, a) - number_count(n-k, a) - number_count(k, a)가 성립한다

 

n!에서 a가 인수로 몇번 들어가는지 결과값을 반환하는 함수를 파이썬 코드로 짜면

def number_count(n, k):
    count = 0
    while n != 0:
        n = n // k
        count += n
    return count

이므로 이를 활용해서 문제를 해결할 수 있다

 

소스 코드

def number_count(n, k):
    count = 0
    while n != 0:
        n = n // k
        count += n
    return count


n, m = map(int, input().split())
count2 = number_count(n, 2) - number_count(n-m, 2) - number_count(m, 2)
count5 = number_count(n, 5) - number_count(n-m, 5) - number_count(m, 5)

print(min(count2, count5))