수학 시리즈: 11051번 이항 계수 2, 1676번 팩토리얼 0의 개수, 2004번 조합 0의 개수 Hint

오늘은 수학 문제들로 준비해봤다.

 

11051번: 이항 계수 2

1676번: 팩토리얼 0의 개수

2004번: 조합 0의 개수

 

11051번 이항 계수 2 문제는 DP를 적용할 수 있는 문제다.

• 문제에서는 (N, K) % 10007을 요구하고 있다. 하지만 우리가 알고 있는 공식 (N, K) = N! / K!(N-K)! 으로 계산한다면 매우 큰 수의 연산을 동반할 것이다.
• 그렇다고 모듈러(%) 연산을 분모, 분자에 분배할 수는 없다. 다시 말하면 (N!) % 10007 / (K!)(N-K)! % 10007과 같은 접근의 결과는 신뢰할 수 없다.
• 점화식을 사용하면 된다. (N, K) = (N-1, K-1) + (N-1, K) 이므로, 모듈러 연산을 두 항에 분배할 수 있다.

 

참조한 질문:

글 읽기 - ★☆★☆★★☆★☆★ 이항 계수 2 FAQ ★☆★☆★☆★

 

1676번 팩토리얼 0의 개수, 2004번 조합 0의 개수는 비슷한 풀이를 갖고 있다.

 

팩토리얼의 뒤 0의 개수를 구하려면 어떻게 해야 할까?

처음에는 팩토리얼을 계산하면서 뒤에 0이 붙으면 이를 카운트하고 10으로 나눈 결과를 배열에 저장해야 하나 싶었다.

명확한 해결 방법은 2와 5를 사용하는 것이다. 팩토리얼 연산에 포함된 2와 5를 카운트하여, 더 작은 개수가 0의 개수가 된다.

 

카운트하는 방법은 두 가지가 있다.

 

첫 번째 방법은 DP와 비슷하다. N! 은 (N-1! 에서의 (2 또는 5)의 개수) + (N이 (2 또는 5)를 갖는 개수)이다. 이 방법은 1676번을 해결한다. 하지만 2004번에서는 시간 초과가 발생한다. 그 이유는 2004번은 N의 최댓값이 2 * 10^9이기 때문이다.

 

두 번째 방법은 수학적 특성을 활용하는 방법이다.

• (N / 5)로 N보다 작거나 같은 5의 배수 개수를 구할 수 있다.
• (N / 25)로 N보다 작거나 같은 25(또는 5*5)의 배수 개수를 구할 수 있다.
• ...

이 개수들을 다 합하면, 이는 N! 에 포함된 5의 개수를 나타내게 된다.

 

예를 들어 25! 의 5의 개수는:

• 25 / 5 = 5: 5, 10, 15, 20, 25가 카운트된다.
• 25 / 25 = 1: 25가 카운트된다.

결과적으로 1~N의 숫자에 대해 각 숫자가 갖고 있는 5의 개수의 합을 구할 수 있게 된다.

 

두 번째 방법은 N!이 몇 번의 반복 계산으로 구해지므로 2004번을 해결할 수 있다. C/C++을 사용한다면 long 타입을 활용하는 것을 잊지 말자.

 

참조한 질문:

글 읽기 - TL뜹니다 이문제에서 벗어나고 싶습니다.

참조 자료:

Count trailing zeroes in factorial of a number - GeeksforGeeks