문제 소개
숫자 k가 주어졌을 때, 1부터 k까지의 모든 값으로 나누어 떨어지는 가장 작은 양의 정수 x를 생각해 보겠습니다. 다시 말해, x가 1부터 k까지의 모든 숫자로 균등하게 나누어질 때의 최솟값을 찾는 것입니다. 우리의 목표는 이 x의 끝에 연속해서 붙어 있는 0(후미 0, trailing zero)의 개수를 구하는 것입니다.
예시
입력이 k = 6이라고 가정해 보겠습니다. 이때 조건을 만족하는 가장 작은 x는 60입니다. 60은 1, 2, 3, 4, 5, 6 모두로 나누어 떨어집니다. 그리고 60의 끝에는 0이 하나만 붙어 있으므로, 출력 결과는 1이 됩니다.
해결 접근 방법
이 문제는 수학적 성질을 활용하면 매우 간단하게 해결할 수 있습니다.
수의 끝에 붙는 0은 곱셈 과정에서 2와 5가 짝을 이루어 만들어집니다. 1부터 k까지의 최소공배수(LCM)에서는 2의 지수가 항상 5의 지수보다 크거나 같기 때문에, 후미 0의 개수는 결국 k 이하의 5의 거듭제곱 개수와 같습니다.
예를 들어 k = 6일 때, 6 이하의 5의 거듭제곱은 5 하나뿐이므로 후미 0의 개수는 1이 됩니다. 이는 앞서 본 예시 결과와 일치합니다.
이를 바탕으로 다음과 같은 단계로 알고리즘을 구성할 수 있습니다.
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- 기준값 x를 1로 초기화합니다.
- x * 5가 k 이하인 동안 반복하며, 반복할 때마다 res를 1씩 증가시키고 x에 5를 곱합니다.
- 반복이 끝나면 res를 반환합니다.
이 알고리즘의 시간 복잡도는 O(log₅ k)로, k가 아무리 커도 매우 빠르게 동작합니다.
구현 코드
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, k):
res = 0
x = 1
while x * 5 <= k:
res += 1
x *= 5
return res
ob = Solution()
k = 6
print(ob.solve(k))입력
6
출력
1
마무리
이처럼 큰 수를 직접 계산하지 않고도, 5의 거듭제곱이 몇 번까지 k 이하에 존재하는지만 세면 원하는 답을 손쉽게 구할 수 있습니다. 실제로 k가 수백만 이상으로 커져도 이 방법은 로그 시간 안에 결과를 반환하므로 효율적입니다.