[BOJ_2004] 조합 0의 개수

문제

(nm)의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

예제 입력 1 복사

25 12

예제 출력 1 복사

2

풀면서 느낀점

입려값이 매우 크기 때문에 최대 1중 for 문 까지 가능하다.

math 라이브러리중 comb라는 툴이 있는데 손쉽게 조합의 숫자를 가져올 수 있다. 하지만 파이썬 3.8부터 가능하므로 사용할 수 없다.

에러코드

import math
n,m = map(int,input().split())

nums = math.comb(n,m)


cnt = 0
while True:
    if not nums %10:
        cnt += 1
        nums //= 10
    else:
        break
print(cnt)

결국은 모든 숫자를 계산해서 가져오는건 무리이므로 끝자리 0의 개수가 나오는 이유를 찾아야 한다.

뒷자리가 0으로 떨어지려면 2와 5의 인수가 곱해질때만 딱 맞아 떨어진다.

100C3 을 했을때 100 x 99x 98 / 3 x 2 x 1 로 인수를 모두 나눌려고 시도했더니 메모리초과가 떴다.

에러코드

n, m = map(int, input().split())

upper = [i for i in range(n, n - m, -1)]
down = [i for i in range(1, m + 1)]

two_counter = 0
five_counter = 0

for i in upper:
    while True:
        if i % 2 == 0:
            two_counter += 1
            i //= 2
        elif i % 5 == 0:
            five_counter += 1
            i //= 5
        else:
            break
for i in down:
    while True:
        if i % 2 == 0:
            two_counter -= 1
            i //= 2
        elif i % 5 == 0:
            five_counter -= 1
            i //= 5
        else:
            break
if m == 0 :
    print(0)
else:
    print(min(two_counter, five_counter))

나의 코드

def five_count(n):
    answer = 0
    while n != 0:
        n = n // 5
        answer += n
    return answer


# n!의 2 개수 세는 함수
def two_count(n):
    answer = 0
    while n != 0:
        n = n // 2
        answer += n
    return answer


n, m = map(int, input().split())

if m == 0:
    print(0)

else:
    print(min(two_count(n) - two_count(m) - two_count(n - m), five_count(n) - five_count(m) - five_count(n - m)))