[파이썬 풀이] 11687번: 팩토리얼 0의 개수 - 백준

백준 11687번: 팩토리얼 0의 개수

알고리즘 분류: 수학, 정수론, 이분 탐색

파이썬(Python) 풀이

 

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

문제

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 찾는 프로그램을 작성하시오.

---

입력

첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.

---

출력

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 출력한다. 그러한 N이 없는 경우에는 -1을 출력한다.

---

풀이

예를 들어 1이 입력되면 0의 개수가 1개인 N은 5이다( 5! = 120이기 때문)

그러면 2가 입력된다면 0의 개수가 2개이므로 N은 10이 된다 ( 10! = 3628800이기 때문)

 

여기까지만 본다면 M과 N의 관계는 M * 5 = N과 같이 보일 것이다.

하지만 M이 5인 경우에는 N은 -1이다. 그 이유는 0의 개수가 4개에서 6개로 바로 올라가기 때문이다.

 

그렇다면 어떻게 접근해야할까?

먼저, 0을 만드는 숫자는 2와 5이다.

그래서 N이 5가 되면 2와 5가 만나서 10(0이 한개)생기고

N이 10이되면 2와, 5와, 10이 만나서 100(0이 두개)생긴다

N이 25가 되면 2, 5, 10, 12, 15, 20, 22, 25(5^2)가 만나서 1000000(0이 6개) 생긴다.

 

정리하자면

0의 개수는 2 * 5의 개수이며, 일반적으로 2의 개수는 5보다 많기 때문에

5의 개수라고 생각할 수 있다.

 

---

 

먼저, 0을 세는 함수를 만들어 주어야 한다.

예를 들어 숫자 X를 입력 받았을 때,

X!의 0의 개수는 X를 5로 나눈 몫을 더하기만 하면 된다.

 

따라서 다음과 같이 코드를 작성할 수 있다.

 

 

그리고 M의 범위가 1 이상이므로, start는 1, end는 입력값 * 5라는 변수를 만들어 준다.

start가 end보다 작거나 같은 경우에 mid = (start + end)로 중간값을 구해주고

count_zero함수에 mid를 넣어서 0의 개수를 확인한다.

0의 개수가 입력값보다 적은 경우에는 start = mid + 1로,

0의 개수가 입력값보다 많은 경우에는 end = mid - 1로 값을 바꿔주고 다시 반복한다.

 

0의 개수가 입력값과 같다면 result의 값을 mid의 값으로 변경해준다.

(왜 result를 처음에 -1로 초기화 해두었나면, 입력받은 0의 개수가 나타나지 않으면 -1을 출력해야하기 때문이다.)

 

따라서 가장 작은 값부터 큰 값 사이를 이분 탐색하면서 찾는 문제라고 생각하면 편하다.