[백준] 2004번 : 조합 0의 개수 (Python)

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

 

 

n과 r이 주어졌을 때,

조합 nCr의 끝자리 0의 개수를 구하는 문제다.

 

 

import sys

#input = sys.stdin.readline
N, M = map(int, input().split()) # N
    
# n!의 5의 개수 세기
def five_count(n):
    answer = 0
    while n != 0:
        n = n // 5
        answer += n
    return answer

# n!의 2의 개수 세기
def two_count(n):
    answer = 0
    while n != 0:
        n = n // 2
        answer += n
    return answer

five = five_count(N)-five_count(M)-five_count(N-M) # n!의 5의 개수
two = two_count(N)-two_count(M)-two_count(N-M) # n!의 2의 개수

print(min(two, five)) # 작은 수가 10의 개수

 

 

[문제풀이]

---

 

이 문제는 조합을 구한 후, 끝자리 0의 개수를 구하면 된다.

조합을 구하는 공식은 이렇다.

 

​​

 

팩토리얼을 구하는 문제의 변형이다.

그러나, 정통적인 방식으로 팩토리얼을 구한 후, 10의 개수를 count하면 시간내에 문제를 풀 수 없다.

 

그래서 10을 이루는 2와 5의 개수를 count해서, 그 중 작은 수를 구한다!