[백준 / BOJ] 2004번 조합 0의 개수 (C++, Python)

링크 : https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

---

문제

---

문제 풀이

이전 문제와 비슷한 유형의 문제지만, 문제 조건에 정수 범위가 2,000,000,000이므로 조금 다른 알고리즘을 써야 하는 문제다.

 

nCm = n! / (n-m)! * m! 이므로, 팩토리얼의 0의 개수를 구했던 것처럼 n!, (n-m)!, m!의 2와 5의 개수를 구하면 되는 문제이다. 어떻게 구하느냐가 관건인데, 이는 간단한 반복문을 통해 구할 수 있다.

 

N!에서 k의 지수 개수를 구하는 방법은 k^i로 N을 계속 나눠주면 된다. 아래 예시들을 보자.

 

4 / 2 = 2 (2, 4)

4 / 4 = 1 (4) 

 

=> 총 3개

 

6 / 2 = 3 (2, 4, 6)

6 / 4 = 1 (6)

 

=> 총 4개

 

25 / 2 = 12 (2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24)
25 / 4 = 6 (4, 8, 12, 16, 20, 24)
25 / 8 = 3 (8, 16, 24)
25 / 16 = 1 (16)

 

=> 총 22개

 

이런 식으로 반복문을 세워주면 된다.

 

파이썬의 경우에는 함수를 하나만 만들고 2와 5를 매개변수로 받아 활용하는 방식으로 구현했다.

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감