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

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

2004번: 조합 0의 개수

 

Difficulty : Silver 2

 

Status : solved

Time : 00:26:27

 

---

 

문제 설명

 

C(n, m) 의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

 

첫째 줄에 정수 n, m(0 <= m <= n <=2,000,000,000, n != 0)이 들어온다.

 

출력

 

첫째 줄에 c(n, m)의 끝자리 0의 개수를 출력한다.

 

입력 예시

 

25 12

 

출력 예시

 

2

 

 

---

 

풀이

 

첫번째. 우선 끝에 나오는 0은 10을 한 번씩 곱했을 때마다 증가한다. 10 = 2 x 5이므로, 전체 조합 계산에서 2의 제곱 및 5의 제곱 중 최솟값이 얼마나 존재하는지 알아내면 바로 답을 구할 수 있다.

 

두번째. C(n, m) = n! / (m! * (n - m)!)으로 이루어진다. 즉 단순히 팩토리얼의 인수를 알아내려면 최대 2000000000번의 반복이 필요하다. 즉 우리는 좀 더 효율적인 방법을 써야 한다. 9!를 예시로 들어보자.

 

9! = 1 x 2 x 3 x 4 x ... 8 x 9

 

여기서 우리는 총 2의 인수가 얼마나 있는지 어떻게 알 수 있을까? 우선 곱해진 수들 중 2를 인수로 갖는 수를 꼽아본다면 (2, 4, 6, 8)이 된다.

하지만 4 = 2^2, 8 = 2^3이므로 단순한 셈으로는 해결되지 않는다. 그렇다면 곱해진 수들 중 2^2 = 4를 인수로 갖는 수를 꼽아본다면 어떨까? (4, 8)로 두 가지가 나온다. 마지막으로 8을 인수로 갖는 수를 꼽는다면 (8)이 된다. 팩토리얼 연산 결과 2의 인수는 총 (4 + 2 + 1) = 7번 등장한다. 이를 히스토그램 형태로 이해한다면 더 쉽다.

 

							O
			O				O
	O		O		O		O
1	2	3	4	5	6	7	8	9

 

이러한 셈법은 인수의 개수를 행 단위로 셈하는 것과 동일하다. 이를 좀 더 일반화한다면, n!에서 d의 인수의 개수는 n보다 작은 모든 d의 제곱꼴의 나눗셈 몫의 총합이 된다.

 

 

 

 

풀이 코드

n, m = map(int, input().split())

def cal_twos_fives(num) :
  twos, fives = 0, 0
  n = 2
  while n <= num :
    twos += num // n
    n *= 2
  n = 5
  while n <= num :
    fives += num // n
    n *= 5
  return twos, fives

twos, fives = cal_twos_fives(n)
for num in [n-m, m] :
  stwos, sfives = cal_twos_fives(num)
  twos -= stwos
  fives -= sfives

print(min(twos, fives))

풀이 완료!