숫자 n이 주어졌을 때, m의 팩토리얼(m!)이 적어도 n개의 0으로 끝나는 가장 작은 수 m을 구하는 것이 이 문제의 목표입니다.
예를 들어 입력값이 n = 2라면 출력은 10이 됩니다. 10! = 3628800으로 끝자리에 0이 두 개 있는 반면, 9! = 362880은 0이 하나뿐이기 때문입니다. 따라서 조건을 만족하는 최솟값은 10입니다.
접근 방법
팩토리얼 값의 끝자리 0은 곱셈 과정에서 2와 5가 짝지어질 때 생성됩니다. 일반적으로 2의 개수가 5보다 훨씬 많으므로, 5의 인수 개수만 세면 됩니다. 이를 위해 다음 단계를 따릅니다.
- count_fives() 함수 정의: n까지의 팩토리얼에 포함된 5의 인수 개수를 계산합니다.
- cnt := 0으로 초기화합니다.
- n > 0인 동안 반복합니다.
- n := (n / 5)의 내림값
- cnt := cnt + n
- cnt를 반환합니다.
메인 로직에서는 이진 탐색(binary search)을 활용해 답의 범위를 좁혀갑니다.
- left := 1, right := 5^24로 초기화합니다.
- right - left > 5인 동안 반복합니다.
- mid := ((right + left) / 10)의 내림값 × 5
- fives := count_fives(mid)
- fives == n이면: right := mid, left := right - 5로 설정한 뒤 반복을 종료합니다.
- fives < n이면: left := mid로 갱신합니다.
- 그 외의 경우: right := mid로 갱신합니다.
- right를 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
def count_fives(n):
cnt = 0
while n > 0:
n = n // 5
cnt += n
return cnt
def solve(n):
left = 1
right = 5**24
while right - left > 5:
mid = int((right + left) / 10) * 5
fives = count_fives(mid)
if fives == n:
right = mid
left = right - 5
break
elif fives < n:
left = mid
else:
right = mid
return right
n = 2
print(solve(n))
입력
2
출력
10
코드 설명
count_fives() 함수는 르장드르 공식(Legendre's formula)을 기반으로 동작합니다. n // 5 + n // 25 + n // 125 ... 방식으로 5의 거듭제곱들이 기여하는 5의 총 개수를 누적하는 원리입니다.
solve() 함수는 탐색 범위를 항상 5의 배수로 유지하면서 이진 탐색을 수행합니다. mid 값을 5의 배수로 맞추는 이유는, 팩토리얼의 0 개수가 5의 배수 지점에서만 변하기 때문입니다. 덕분에 조건을 만족하는 가장 작은 m을 빠짐없이 찾을 수 있습니다.
이 알고리즘의 시간 복잡도는 O(log m × log₅ m) 수준으로 매우 효율적이며, n이 큰 경우에도 빠르게 답을 구할 수 있습니다.