[BEAKJOON] 백준 2004번 : 조합 0의 개수

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

2004번: 조합 0의 개수

문제

접근

이전 팩토리얼 문제를 풀어봤으면, 한 팩토리얼 값의 5의 승수가 겹치는 수를 구해야한다.

문제는 nCr의 값을 구하는 것이기 때문에, 이항 계수의 공식을 생각하면 된다. 이항 계수의 공식은 팩토리얼 값으로 이루어져 있어서 이를 이용하면 쉽게 풀 수 있을 것이다.

 

조합은 영어로 combination이며, 고교 수학 내에서는 대문자 C를 사용하여 표현한다.

조합의 뜻은, nCr 의 뜻은 'n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수' 이다.

 

일단 이항 계수를 구하는 공식은 다음과 같다.

 

이렇게 식으로 나타낼 수 있다.

 

풀이방법, 문제 봉착

사실 앞서 팩토리얼 문제는 당연히 2는 넘쳐 남으니까, 5에 대해서만 다루어줬는데, 5만 다루어주니까,

해당 문제에서는 "틀렸습니다"가 나온다.

 

https://www.acmicpc.net/board/view/323

글 읽기 - 채점 데이터에 취약점?같은게 있는것같습니다

 

문제에서 예시로준 25C12는 맞지만, 20C16은 올바른 값이 나오지 않는다.

 

그러면 2의 대한 것도 체크하고, 그 중에서 작은 수를 출력해주면 된다.

 

정답 코드

n, r = map(int, (input().strip()).split())
count_n_f = n
count_n_t = n
count_f = 0

while (count_n_f // 5 != 0):
    count_f += 1
    count_n_f //= 5

result_sum_f = 0
for i in range(1, count_f + 1):
    result_sum_f += n // (5 ** i)
for i in range(1, count_f + 1):
    result_sum_f -= r // (5 ** i)
for i in range(1, count_f + 1):
    result_sum_f -= (n - r) // (5 ** i)

count_t = 0
while (count_n_t // 2 != 0):
    count_t += 1
    count_n_t //= 2

result_sum = 0
for i in range(1, count_t + 1):
    result_sum += n // (2 ** i)
for i in range(1, count_t + 1):
    result_sum -= r // (2 ** i)
for i in range(1, count_t + 1):
    result_sum -= (n - r) // (2 ** i)

print(min(result_sum, result_sum_f))