백준 2004. 조합 0의 개수

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

2004번: 조합 0의 개수

당연하지만 일반 팩토리얼로 풀리지 않는다. 그래서 조합 공식인 n!/r!(n-r)!에서, 분자에서의 2와 5의 수, 분모에서의 2와 5의 수를 찾아서 뺄 생각을 했다. 10^n승은 (2x5)^n이므로 2와 5 중에 더 적은 녀석만 구해준다면 10의 계수를 알 수 있다.

다만 구현하는 데 좀 애를 먹었다.

def count_two(n):
	count = 0
	while n != 0:
		count += n//2
		n //=2
	return count

def count_five(n):
	count = 0
	while  n != 0:
		count += n//5
		n//=5
	return count

n, r = map(int, input().split())
print(min(count_two(n) - (count_two(n-r) + count_two(r)), count_five(n) - (count_five(n-r) + count_five(r))))

인수분해를 구현했다.

5도 똑같은 개념이다. 연속되는 수열에서 2로 나눠지는 수는 모든 수열을 2개씩 묶은 만큼, 즉 n//2만큼 존재하고, 5로 나눠지는 수는 모든 수열을 5개씩 묶은 만큼 존재한다. 그렇게 나눈 수는 (다른 수 뭉탱이) * 팩토리얼 꼴로 나타낼 수 있으므로 반복할 수 있다.

 

이 때 1로 인수분해 하는 것은 2가 없다는 뜻이므로, n//2가 되면 반복을 중단하면 된다.