BOJ 2004, 1676 - 팩토리얼에 대한 접근

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

2004번: 조합 0의 개수

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

1676번: 팩토리얼 0의 개수

 

강의에서 배운 팩토리얼 문제에 대한 접근을 정리해볼까 한다.

1676번 문제를 먼저 살펴보자. 

 

어떤 수 N이 주어졌을 때, 이 수의 팩토리얼의 값에서 0은 몇 개 일까? (잠시 고민해보자.)

다음과 같은 방법을 생각할 수 있을 것이다.

1. 팩토리얼 값을 계산한 뒤, 0을 센다. (N /= 10과 N % 10 == 0을 이용)
2. 결국 10이란 2와 5의 곱이니까.. 소인수분해를 통해 2의 갯수를, 5의 갯수를 각각 파악해서 더 적은 걸 선택하자.
3. 2의 갯수보다, 5의 갯수가 무조건 적을테니 5의 갯수만을 파악하자!

예전에 나라면, 먼저 1번을 생각하고, 이후에 2번까지는 여차저차해서 생각해냈을 것이다. 하지만 결국 이 문제의 핵심은 5의 갯수가 더 적음을 알고, 이를 이용하는 3번 방법을 떠올리는 것이다.

 

즉 어떠한 N에서 5의 갯수 D(N)은 다음과 같이 나타낼 수 있다.

D(N) = [N/5] + [N/5^2] + [N/5^3] + ...

식보다는 그림이 더 잘 이해가는 사람을 위해 그림도 첨부하면 다음과 같다.

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

위 표에서 노란색으로 칠해진 숫자의 경우 5를 하나 가지는 수이다. 빨간색은 5를 두 개 가지는 즉, 5^2의 배수이다.

 

저 표를 보면서, 위 식에 100을 대입해 보자.

 

먼저 100을 5로 나누면 20이다.  => 인수로 5를 1개 이상 가지는 수의 갯수

또 100을 5^2로 나누면 4이다. => 인수로 5를 2개 이상 가지는 수의 갯수

즉, 100!의 0의 갯수는 5의 갯수가 20 + 4로 24개이다.

 

이제 2004번 문제를 보자. 

 

2004번 문제의 경우, 어떤 수 n과 m이 주어질 때, nCm의 결과값에서 0의 갯수를 파악하는 문제이다.

nCm = n! / (n - m)! m! 이니, n의 10의 갯수에서 (n - m)과 m의 10의 갯수를 빼면 된다.

다만 조합의 경우엔, 2가 5보다 적을수도 있기 때문에, 각각의 경우에 대해서 2와 5가 몇 개인지를 파악해줘야 한다.

 

이제 D(N)의 식을 고쳐보도록 하자.

D(N)_2 = [N/2] + [N/2^2] + ...
D(N)_5 = [N/5] + [N/5^2] + ...
D(N) = min(D(N)_2 , D(N)_5)

위 식을 이용하면 2004번 문제를 해결가능하다. 위 방법은 매우 유용하니 항상 기억해두도록 하자.