[백준] 2004번 (python 파이썬)

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

 nCr = n!/(n-r)!r! 을 이용하면 된다.

하지만 단순 팩토리얼을 이용하여 풀면 n, m 이 20억이될 수 있기 때문에 시간초과, 또는 메모리 초과가 될 것이다.

 

끝자리가 0이라는 것은 2 와 5의 곱으로 이루어 졌으면 0이 된다.

만약 xxxxx00 이면 2가 2개 5가 2개의 곱으로 이루어 졌다는 것이다.

즉, 2, 5의 쌍을 구하면 0의 갯수를 구할 수 있다.

 

하지만 이것도 반복문으로 돌리다보니 계속 시간초과가 났다... 도저히 모르겠어서 답을 본 결과...

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

이런식으로 2의 갯수를 구하는 것을 알 수 있었는데....

사실 이 식만봤을때 뭔소린지 이해를 못했다... 

8! = 8 7 6 5 4 3 2 1 => 2가 나오는 횟수 7번이다

왜냐

8 = 2x2x2

6 = 2x3

4 = 2x2

2 = 2x1

으로 2가 7번나온다.

제곱수인 4는 2가 2번

3제곱수인 8은 2가 3번 나오는 것을 알 수있다.

 

여기서 알수있는것이 먼저 8 7 6 5 4 2 1에서 2의 배수의 갯수를 구한다. 8/2 = 4

다음으로 제곱수에 대해서 배수를 구한다. 8/(2*2) = 2

다음으로 세제곱수에 대해서 배수를 구한다. 8/(2*2*2) = 1

즉 4 + 2 + 1이란 것이다.

 

한번더 100으로 예시를 들면....

100!을 생각해 봤을 때, 5가 곱해진 개수를 구해해보자.

일단 100까지의 수 중에서 5의 배수들이 5를 1개씩 가지고 있음을 알고 있다.

100까지의 5의 배수는 20개 이므로 100/5=20을 먼저 구한다.( 5, 10, 15, 20, 25 ... 100 이는 5를 1개이상씩 가지고있다 )

여기서 5의 지수가 2인 애들을 보면 5^2의 배수들(25, 50, 75, 100)이 5를 하나씩 더 가지고 있음(2개)을 알 수 있다

따라서 기존에 20에다가 100/5^2=4 를 더해준다.

 

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)))

 

 

참고

• insight-bgh.tistory.com/337