백준 조합 0의 개수 - 2004

문제링크

https://www.acmicpc.net/problem/2004

풀이

Before : z nCr = n! / (r!*(n-r)!) 위에 3개의 팩토리얼을 각각 구해서 위에 계산식을 풀고 거기서 0의 갯수를 구할려고 했었음. 그러나 이는 n, r이 20억개일 때에는 당연히 시간초과가 날 수 밖에 없음 따라서 다른 방법을 사용해야함

After : 일단 뒤에 0의 갯수를 구할려면 number*10^n 에서 n이 0의 갯수에 해당한다. 따라서 10의 소인수 분해인 2 와 5 의 쌍 형태를 팩토리얼에서 찾아내야 한다. 그렇다면, 우리는 0의 개수가 주어진 수의 2가 몇번나누어지는지와 5가 몇번 나누어지는지를 구하고 2 와 5의 개수중 더 작은 개수를 선택하면 됨 그런 다음 지수의 차 개념을 적용하면 됨

코드

# factorial에서 해당 number가 몇번 들어가는지 count

def count5(num):
    
    cnt = 0
    while num > 0:
        num = num // 5
        cnt += num

    return cnt

def count2(num):
    
    cnt = 0
    while num > 0:
        num = num // 2
        cnt += num

    return cnt

# 5와 2가 쌍을 이뤄서 10을 만들어 냄 = 0의 갯수
# 따라서 count된 수 중에 더 작은 것을 선택

def min_count(n, m):

    # 지수의 차 개념 적용 
    temp5 = count5(n) - count5(m) - count5(n-m) 
    temp2 = count2(n) - count2(m) - count2(n-m)

    return min(temp5, temp2)



if __name__ == '__main__':
    n, m = map(int, input().split())
    print(min_count(n, m))

느낀점

사실 문제의 이해도 어려웠을 뿐더러, 해설의 이해도 어려웠음 이러한 아이디어를 떠올리는 것은 아무리 해도 늘 것 같지 않아서 그냥 여러문제를 풀고 그 문제들을 익히는 방법을 택하는게 best!