[BOJ/Python] 2004_조합 0의 개수

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

2004번: 조합 0의 개수

 

문제

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 nCm의 끝자리 0의 개수를 출력한다.

예제 입력 1 

25 12

예제 출력 1 

2

 

---

풀이

 

조합 문제라서 그냥 무턱대고 math모듈을 import해서 math.comb(n,m)을 이용해 조합을 구하고, 0의 개수를 세는 방식으로 문제를 풀려고 했으나, 당연하게도 시간초과가 나왔다. nCm의 경우 (n!)/(m!)((n-m)!)을 계산해야하는데, 이 문제에서 정수의 범위가 무려 2,000,000,000까지 가능하기 때문에 시간초과가 나오는게 당연했다.

import sys
import math
 
n,m = map(int,sys.stdin.readline().split())
result = str(math.comb(n,m))
count = 0
 
for i in range(1,len(result)+1):
    if result[-i]=='0':
        count+=1
    else:
        break
 
print(count)

(시간초과가 나온 잘못된 코드)

 

팩토리얼을 직접 계산하면 시간초과가 나오고, 정수의 범위가 매우 넓기 때문에 직접 계산하여 푸는 문제는 아니라고 생각했다.

 

문제에서 끝자리 0의 개수를 구하라고 하였고, 이는 계산된 결과값에 10이 몇번 곱해져있는가를 생각하면 알 수 있다. (10이 1번 곱해져있으면 0이 1개, 2번 곱해져있으면 0이 2개이다. 결국 10의 지수를 구하는 문제이다.)

그리고 10은 2와 5의 곱이므로, 10의 지수는 2의 지수와 5의 지수 중 더 작은 값이 되고, 최종적으로 이 문제는 nCm에서 2의 지수와 5의 지수 중 작은 값을 구하는 문제가 된다.

 

지수법칙을 이용하면, 곱셈과 나눗셈을 지수들의 덧셈과 뺄셈으로 계산할 수 있고, 따라서 (n!)/(m!)((n-m)!) 식을 이용하면,

5의 지수의 경우 (n!의 5의 지수)-(m!의 5의 지수)-((n-m)!의 5의 지수)이고,

2의 지수의 경우 (n!의 2의 지수)-(m!의 2의 지수)-((n-m)!의 2의 지수)라고 할 수 있다.

n!의 5의 지수는

n! = 1*2*3*4*5*6*7*...*(n-1)*n 이므로, n//5 + n//25 + n//125 + ... 의 계산을 통해 5의 지수를 구할 수 있다.

n//5를 하게 되면, n이하 5의 배수의 개수를 구할 수 있다. ( 5의 지수를 갖고 있는 수)

n//25를 하게 되면, n이하 25의 배수의 개수를 구할 수 있고, 25의 배수의 경우 5의 제곱이므로, 5의 지수를 두개 가지고 있지만, 이미 n//5에서 5의 배수에 포함되므로 두번 셀 필요 없이 한번만 더 해준다.

n//125의 경우도 마찬가지이다.

이는 2의 지수를 구하는 경우에도 마찬가지이므로, 코드를 작성해보면 다음과 같다.

 

import sys
 
n,m = map(int,sys.stdin.readline().split())
 
def div(n,num):
    count = 0
    while n>=num:
        count += n//num
        n = n//num
    return count
 
print(min(div(n,5)-div(m,5)-div((n-m),5),div(n,2)-div(m,2)-div((n-m),2)))

 

5의 지수와 2의 지수를 구하고, min을 이용하여 더 작은 지수 구하고, 이게 곧 10의 지수이므로 출력한다.