문제
n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.
nCm은 수식으로 n!/m!(n-m)! 으로 구할 수 있다. (5! = 1 * 2 * 3 * 4 * 5)
n과 m이 주어졌을때 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n, m(0≤m≤n≤1,000,000)이 들어온다.
출력
첫째 줄에 0의 개수를 출력한다.
예제 입력
25 12
예제 출력
2
아이디어
nCm의 끝자리 0에 개수를 구하려면 0이 되는 조건을 알아봐야 된다. 1 ~ 9까지 숫자에서 서로 곱해서 10의 배수가 되는 경우는 2와 5를 곱했을 경우이다. 문제서 나와있듯이 nCm은 수식으로 n!/m!(n-m)!으로 구할 수 있다. 여기서 규칙을 찾을 수 있는게 0의 개수는 2와 5의 지수중에 최소값이 0의 개수이다. n = 10, m = 5로 예를 들어 보면 10!/5!(10-5)! -> 3628800 / 120 * 120이 된다. 소인수분해를 해보면 52 * 28 * 34 * 71 / (51 * 23 * 3) * (51 * 23 * 3)이 된다. 즉 여기서 2의 지수와 5의 지수중에 작은 값이 0의 개수가 된다. 5의 지수는 52-1-1이므로 0, 2의 지수는 28-3-3이므로 2이다. 따라서 최소 지수의 수가 0이므로 0의 갯수도 0이 된다. 이 내용을 바탕으로 아래와 같이 코드를 구현했다.
코드
풀이보기(클릭)
1
2
3
4
5
6
7
8
9
10
11
12
13
N, M = map(int, input().split())
def count_num(n,k):
count = 0
while n:
n //= k
count += n
return count
five_count = count_num(N, 5) - count_num(M, 5) - count_num(N - M, 5)
two_count = count_num(N, 2) - count_num(M, 2) - count_num(N - M, 2)
print(min(five_count,two_count))
문제 출처
ALGORITHM JOBS