문제 설명

이번 포스팅은 백준 2004번: 조합 0의 개수 문제에 대한 기록입니다.

문제를 간단히 요약하면,
"n과 m이 주어졌을 때 $nCm$의 끝자리 0의 개수를 출력하는 문제"입니다.

풀이

nCm을 직접 계산하면 안될까?

---

가장 단순하게 문제에 접근하면, "$nCm$을 직접 계산한 다음 끝에 있는 0의 개수를 구하면 되겠네!" 라고 생각할 수 있습니다.

그러나 $nCm$ 계산에는 팩토리얼 연산이 포함됩니다.

위 그림은 Big-O Complexity를 나타낸 그래프입니다. 팩토리얼을 나타내는 것은 가장 위로 솟구치고 있는 하늘색 그래프...

네, 가능하면 팩토리얼 연산은 피하는 것이 좋으며 문제의 조건이, $0 \le m \le n \le 2,000,000,000$, $n \ne 0$ 이므로 제한시간에도 걸리게 될 것입니다.

끝자리에 0은 언제 생길까?

---

단순하게 직접 계산할 수 없다면, 문제를 하나씩 뜯어보며 접근할 필요가 있습니다.

이 문제에서 궁극적으로 구해야 하는 것은 "$nCm$의 끝자리 0의 개수"입니다.

그렇다면 끝자리에 0은 언제 생길까요? 끝자리에 0들이 붙는 수는 예를 들어 10, 50, 100, 200, 1000, ...

네, 맞습니다. 10의 거듭제곱을 포함하고 있는 수 입니다. $10^n$을 포함하고 있는 수는 끝자리에 0이 $n$개가 나타나게 됩니다.

즉, $nCm$의 소인수분해에 2*5가 몇 개 포함되어 있는지 를 알면 끝자리에 오는 0의 개수를 알 수 있습니다.

따라서, $nCm$에 포함된 2와 5의 개수를 각각 센 다음, 둘 중 더 작은 개수가 끝자리 0의 개수가 됩니다. (2*5의 형태가 만들어지기 위해선 짝이 맞아야 하기 때문)

nCm가 인수로 포함하고 있는 2와 5의 개수 구하기

---

$nCm$이 포함하고 있는 2와 5의 개수를 어떻게 셀 수 있을까요?

$nCm$은 $\frac{n!}{m!(n-m)!}$ 입니다.

따라서 2의 개수는, $n!$이 포함하는 2의 개수 - $m!$이 포함하는 2의 개수 - $(n-m)!$이 포함하는 2의 개수 가 됩니다. 5도 같은 방식으로 구할 수 있겠죠.

그럼 이제 $n!$에 인수로 포함된 $k$의 개수를 구하는 방법만 알아내면 이 문제는 다 푼 겁니다.

n!가 인수로 포함하고 있는 k의 개수 구하기

---

$n!$에 인수로 포함된 $k$의 개수는,

"n 이하의 범위에서 $k^1$, $k^2$, $k^3$ ... 의 배수를 모두 카운트하여 더하는 것" 으로 구할 수 있습니다.

예를 들어, $10!$에 인수로 포함된 2의 개수를 구한다고 한다면,

먼저 $2^1$의 배수를 세면 2, 4, 6, 8, 10 -> 5개. 이때 $4 = 2^2$, $8 = 2^3$ 처럼 $2^2$를 포함하는 수의 인수 2는 모두 카운트되지는 못합니다.

그 다음 $2^2$의 배수를 세면 4, 8 -> 2개. 이때는 이전에 카운트되지 못했던 4에 포함되었던 2까지 모두 카운트됩니다. 아직 $2^3$을 포함하는 8에 포함된 2는 하나가 카운트되지 못합니다.

마지막으로 $2^3$의 배수를 세면 8 -> 1개. 8에 포함되었던 2까지 모두 카운드됩니다.

10!은 $1*2*3*...*10$ 이므로, 결과적으론 1~10 에 인수로 들어가 있는 2가 모두 합쳐지게 됩니다. 따라서 $10!$에 인수로 포함된 2의 개수는 5+2+1 = 8이 됩니다.

이를 함수로 작성하면 아래와 같아집니다.

def count_k(n, k):
    result = 0
    temp = k

    while temp <= n:
        result += n // temp
        temp *= k

    return result

위 함수를 이용하여 $nCm$에 포함된 2와 5의 개수를 각각 구하고 둘 중 작은 것, 즉 끝자리 0의 개수를 출력하는 코드를 작성하면...

two = count_k(n, 2) - count_k(m, 2) - count_k(n-m, 2)
five = count_k(n, 5) - count_k(m, 5) - count_k(n-m, 5)

print(min(two, five))

문제 해결!!

결과 코드

from sys import stdin

n, m = map(int, stdin.readline().split())

def count_k(n, k):
    result = 0
    temp = k

    while temp <= n:
        result += n // temp
        temp *= k

    return result

two = count_k(n, 2) - count_k(m, 2) - count_k(n-m, 2)
five = count_k(n, 5) - count_k(m, 5) - count_k(n-m, 5)

print(min(two, five))