[백준 2004 파이썬] 조합 0의 개수 (실버2, 조합론)

알고리즘 유형 : 조합론
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

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

def count2(N):
    if N < 2:
        return 0
    
    count = 0
    while N >= 2:
        count += N//2
        N = N//2
    return count

def count5(N):
    if N < 5:
        return 0
    
    count = 0
    while N >= 5:
        count += N//5
        N //= 5
    return count

two_count = count2(n) - count2(n-m) - count2(m)
five_count = count5(n) - count5(n-m) - count5(m)
print(min(two_count, five_count))

풀이 요약

1. 1676 팩토리얼 0의 개수에서 사용한 원리를 일부 사용한다.

2. 다만 이 문제는 $_{n}\mathrm{C}_{r}$의 뒤에서부터 0이 아닌 수를 만날 때까지의 0의 개수를 구해야한다.

   $_{n}\mathrm{C}_{r}$의 최종적인 값은 팩토리얼 형태가 아니므로, 5의 지수만을 고려해서는 안된다. 이 경우에는 2의 지수, 5의 지수를 둘다 구해서 둘 중 작은 값을 답으로 취해야한다. 분자와 분모 각각은 팩토리얼로만 이루어져 있지만, 나눠지면서 2의 지수와 5의 지수의 규칙에 변동이 생기기때문이다.

   예를 들어, 6C2의 경우 값은 15이고, 3x5, 5의 지수가 2의 지수보다 더 크다.

3. $_{n}\mathrm{C}_{r}$ = n!/(n-r)!r! 이라는 공식을 활용한다. 그리고,

   2의 지수 = n!의 2의 지수 - (n-r)!의 2의 지수 - r!의 2의 지수

   5의 지수 = n!의 5의 지수 - (n-r)!의 5의 지수 - r!의 5의 지수

4. 팩토리얼의 5의 지수 구하는 법은 지난 1676번 문제에서 배운 걸 그대로 써먹으면 된다.

   n!에 대해, n//5 + n//25 + n//125 +... 이다.

   그리고 이 것은 2의 지수 구할 때도 유효한 방법이다. n//2 + n//4 + n//8 + n//16 +...

5. 2의 지수와 5의 지수 중 작은 값이 답이다.

배운 점, 어려웠던 점

• n!의 5의 지수 구하는 법을 알게되고나니 2의 지수 구하는 법도 동일하게 적용된다는 것을 쉽게 알 수 있었고, 구현도 어렵지 않았다. 1676 팩토리얼 0의 개수 문제를 풀 줄 알면 쉽게 푸는 문제인 것 같다.