[백준 / BOJ] 1676번 팩토리얼 0의 개수 (C++, Python)

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

1676번: 팩토리얼 0의 개수

---

문제

---

문제 풀이

나의 수학실력에 다시 한번 감탄하게 된 문제다. 분명 난이도는 실버 5인데 풀리지가 않아서..

 

당연하게도 N이 500까지이므로 N!을 직접 구해 해결하는 방법은 불가능하다. 이 문제의 핵심은 뒤에 0이 나오는 경우는 10이 곱해졌을 때라는 것을 알아차리는데에 있다. 그렇다면 0의 개수는 어떻게 구할까?

10의 0의 갯수는 1개이고, 이는 2 x 5다.

100에서 0의 갯수는 2개이고, 이는 2 x 2 x 5 x 5다.

200에서 0의 갯수는 2개이고, 이는 2 x 2 x 2 x 5 x 5다.

1000에서 0의 갯수는 3개이고, 이는 2 x 2 x 2 x 5 x 5 x 5다.

 

요점은 10이 몇번 곱해졌는지를 알아야 하고, 이는 소인수분해 했을 때 5의 개수와 같다. (2보다 5가 적게 나오기 때문에)

그러므로 N!은 N * (N-1) * (N-2) ...와 같으니 N을 입력받았을 때 1부터 N까지 각각의 수마다 5가 얼마나 나오냐를 체크해주면 된다.

 

+) 파이썬 코드를 찾아보던 중 이 분의 풀이가 신박한 것 같아 첨부해봅니다.

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감

수학은 너무.. 어렵다..