[백준] 조합 0의 개수

출처:: www.acmicpc.net/problem/2004

분류:: 수학

 

1. 문제 이해 및 해결과정

-n이 20억이다. 조합식으로 계산하는 코드를 만들었는데, 시간초과다 - 0이 생기는 경우를 고민해보면, 10은 즉, 2과 5의 곱으로 만들어진다 - 조합에서 0이 되려면 약분 후에 10의 배수(2*5)가 분자에 있으면 된다 - nCm = n! / m! (n-m)!  팩토리얼부분을 분자 A, 분모 B,C 라고 하면 A,B,C가 2로 나누어떨어지는 횟수를 구하여 A-(B+C)를 하고 , 5로 나누어 떨어지는 횟수를 A-(B+C) 를 하여 더 작은 값이 답이 된다.

2. 풀이방법

 1. 

#조합 0의 개수
#https://www.acmicpc.net/problem/2004
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())

def divide_two(x): #2로 몇번 나누어떨어지는지
    cnt=0
    while x!=0:
        x//=2
        cnt+=x
    return cnt

def divide_five(x): #5로 몇번 나누어지는지
    cnt=0
    while x!=0:
        x //= 5 
        cnt += x
    return cnt

if n==0:
    print(0) #n!은 0
else:
    print(min(divide_two(n)-(divide_two(m)+divide_two(n-m)),divide_five(n)-(divide_five(m)+divide_five(n-m))))

 

 

3. 오답원인

 1. 시간초과

#조합 0의 개수
#https://www.acmicpc.net/problem/2004
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
m=min(m,n-m)
num=1
nanu=1
for i in range(m):
    num*=n-i
for i in range(1,m):
    nanu*=i
num=num//nanu
num=list(str(num))
cnt=0
for i in range(len(num)-1,0,-1):
    if num[i]!='0':
        break
    else:
        cnt+=1
print(cnt)

 

4. 알게된 점