[백준] 2004 조합 0의 개수

www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

def numof5(number):
    result = 0
    while True:
        if number % 5 == 0:
            result += 1
            number/= 5
        else:
            break
    return result
        
n,m = map(int,input().split())

#tmp1= n-m+1
tmp1=0
for i in range(n-m+1,n+1):
    tmp = str(i)
    if tmp[-1] =='5' or tmp[-1] =='0':
        tmp1+=numof5(i)

#tmp2= n-m
tmp2=0
for i in range(1, n-m+1):
    tmp = str(i)
    if tmp[-1] =='5' or tmp[-1] =='0':
        tmp2+=numof5(i)

print(tmp1-tmp2)

첫번째 시도: 시간초과

---

import sys
def numof5(number):
    result = 0
    while (number % 5 == 0):
        result += 1
        number/= 5

    return result
input=sys.stdin.readline
n,m = map(int,input().split())

lst_tmp1=[i for i in range(n-m+1,n+1) if not i % 5 ]
num_tmp1=list(map(numof5,lst_tmp1))
lst_tmp2=[i for i in range(1,n-m+1) if not i % 5 ]
num_tmp2=list(map(numof5,lst_tmp2))
print(sum(num_tmp1)-sum(num_tmp2))

두번째 시도 메모리 초과

---

n,m = map(int,input().split())
def num_5(n):
    count = 0
    while n != 0:
        n = n // 5
        count += n
    return count

result = num_5(n) - num_5(m) - num_5(n-m)

print(result)

세번째 시도 틀림

---

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

def num_5(n):
    count = 0
    while n != 0:
        n = n // 5
        count += n
    return count

def num_2(n):
    count = 0
    while n != 0:
        n = n // 2
        count += n
    return count

total_2 =  num_2(n) - num_2(m) - num_2(n-m)
total_5 = num_5(n) - num_5(m) - num_5(n-m)

answer = min(total_2, total_5)
print(answer)

팩토리얼을 보면 항상 5보다 2가 더 많기 때문에 5만 찾으면 될줄 알았으나 5C4의 경우 0이 없는데 1이 나오는 경우가 있었다. 그래서 2도 찾아서 더 작은걸 찾으니 성공하였다.

5와 2의 개수를 구하는 알고리즘이 이해가 가지 않는다면 링크를 타고 가서 보면 된다. 설명이 잘 되어있다.

ksj14.tistory.com/entry/BackJoon1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98

[BaekJoon][1676] 팩토리얼 0의 개수

---

내 코드는 거의 없지만 공부를 위해 적어놓는다