2004 - 조합

nCm 에 대해서 오른쪽부터 0의 개수를 출력하는 문제이다.

nCm = (n! / m!) / (n-m)! 이다. 여기서 m≤n≤2,000,000,000 인데 각각 팩토리얼을 계산한다면 절대 구할 수 없을 것이다. (오버플로우나 시간복잡도 등..)

이 문제 이전에 일반적인 nCm 을 구하는 문제부터 짚어보자.
오버플로우를 피해서 nCm을 구하는 것이라면 각 팩토리얼을 모두 계산 후에 나누는 게 아니라 분자(2 * 3 *... * n-m+1) 와 분모(2 * ... * m) 을 구성하는 각 숫자를 하나씩 계산하는건데

12C5 를 예로 들자면 12! 을 계산 후에 5! 7! 으로 나누는게 아니라 아래와 같이 진행한다.
12C5는 아래와 같이 나타낼 수 있다.
( 12 * 11 * 10 * 9 * 8 ) / ( 5 * 4 * 3 * 2 * 1 )
위 식은 다시말해 (12/5) * (11/4) * (10/3) * (9/2) * (8/3) 을 따로 한 것과 같은 결과이다.

그럼 0의 개수는 어떻게 구할까?
0의 개수를 구하는 문제는 보통 숫자를 소인수분해해서 2의 지수갯수와 5의 지수갯수 중 더 작은 만큼이 0의 갯수를 구성하는 게 일반적이다.
예를들면 120 = 2³ * 3¹ * 5¹ = 2¹ * 3¹ * 10¹ 이라서 가능하다.

서론이 길었는데, 다시 본문으로 돌아와서.
이 문제에서는 nCm을 구하는게 아니라 nCm의 0의 개수를 구하는 문제이니, [분자에서 나온 2^a * 5^b]와 [분모에서 나온 2^c * 5^d] 를 구해서 a-c 와 b-d 중에 더 작은 값이 곧 nCm의 0의 개수가 된다.

N=9 으로 생각해보자.
N! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 이 될 것이다.
여기서 2의 배수만 추려낸다면 2의 지수를 구할 수 있을 것이다.
2의 배수 = N/2 개만큼 있다. = 4개 ( 2, 4, 6, 8. )   --- 여기서 2의 배수만 구했는데, 그럼 2, 4, 6 이 각각 2¹ 을 가지고 있다는 뜻이된다.
4의 배수 = N/4 개만큼 있다. = 2개 ( 4, 8. )       ---- 2¹에 대해서 앞에서 더해줬기 때문에 지금 센 것이 중복일 지 몰라도 잘 생각해보면 "중복을 피했다"

마찬가지로 8의 배수, 16의 배수... 에 대해서 반복하면 된다.
5의 배수도 위와 같이 세면 된다.

수학적인 사고가 부족해서 위 개념을 이해하는 데 한참 걸렸다. 답답함을 안고 알려준 친구에게 고마움을 표한다.