(Python/🥈2)백준 알고리즘 2004번: 조합 0의 개수

문제 출처:https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

풀이:

import sys
from math import factorial

n, m = map(int, input().split())
res = factorial(n) // (factorial(m) * factorial(n - m))

res_list = list(map(int,str(res)))
res_list.reverse()

count = 0
for i in res_list:
    if i == 0:
        count += 1
    if i != 0:
        break

print(count)

시간 초과가 나왔다.n이 200만까지다 ,,

 

정답 풀이:

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

def two_count(n):
    two = 0
    while n != 0:
        n = n // 2
        two += n
    return two

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

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

 

몇시간을 생각해도 도저히 모르겠어서 정답코드를 봤는데 이게 가장 이해하기 쉬웠다.

 

각 받은 수의 제곱수로 나눈 몫을 two 나 five에 넣어주면 된다.

 

맨 마지막 출력은

 

five_count = count_number(N, 5) - count_number(M, 5) - count_number(N - M, 5) 
two_count = count_number(N, 2) - count_number(M, 2) - count_number(N - M, 2)

# 이거 중에 작은거를 출력하는 것이다. 2, 5 가 똑같아야 10이 돼서 끝자리가 0이기 때문이다.

 

출처:https://tmdrl5779.tistory.com/95