2022-07-03 @이영훈
첫번째 풀이
10과 5와 2의 배수를 각각 구하는 방식
n = int(input())
count_10 = 0
count_2 = 0
count_5 = 0
for num in reversed(range(1, n + 1)):
while num % 10 == 0:
count_10 += 1
num = num // 10
while num % 5 == 0:
count_5 += 1
num = num // 5
while num % 2 == 0:
count_2 += 1
num = num // 2
zeros = count_10
zeros += min(count_2, count_5)
print(zeros)
Python
복사
개선된 두번째 풀이
5의 개수만 찾는 방식. O(n^2)
숫자 5뒤에는 2는 항상 더 충분히 있기 때문에 5의 개수만 찾으면 됩니다
5! = 5 * 4 * 3 * 2 * 1
5뒤에 숫자 4와 2가 있어서 5만 있다면 2는 세지 않아도 됩니다.
참고로 50!에서 5의개수는 12개, 2의 개수는 47개입니다
n = int(input())
count = 0
for num in reversed(range(1, n + 1)):
while num % 5 == 0:
count += 1
num = num // 5
print(count)
Python
복사
더 개선된 세번째 풀이
5의 배수를 O(n)으로 찾는 방법
생각해보면 5의 배수를 찾는 방법은 규칙성이 있습니다
10! = 10*9*8*7*6*5*4*3*2*1
5, 10으로 5씩 증가하므로 10!에서 5의 배수 개수는 10을 5로 나눈 몫(10//5)과 같습니다
그런데 25, 125와 같이 5가 여러번 반복되는 수가 있습니다
25! = 25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1
25, 20, 15, 10, 5는 5의 배수입니다 5의 단순 배수 개수는 25//5 = 5개입니다
그런데 5의 두번 배수는 25, 20, 15, 10, 5에서 5의 배수 중에서 5번째에 등장합니다
그래서 25를 5로 나눈 몫인 5(25//5 = 5)에서 다시 5로 나누면 됩니다 (5//5 = 1)
같은 방법으로 5의 세번 배수(125, 250,,,) 개수는 5를 세번 나눈 몫입니다
n = int(input())
count = 0
while n > 1:
count += n // 5
n = n // 5
print(count)
Python
복사