[Python] 백준 2004 조합 0의 개수

코드 작성

def cnt2(n):
    two = 0
    while n != 0:
        n = n//2
        two += n
    return two
def cnt5(n):
    five = 0
    while n != 0:
        n = n//5
        five += n
    return five

n, m = map(int, input().split())
print(min(cnt2(n)-cnt2(n-m)-cnt2(m),cnt5(n)-cnt5(n-m)-cnt5(m)))

코드  풀이

#1. 콤비네이션

nCr = n! / { (n-r)! * r ! } 식을 활용하여

(1) n의 2배수 - n-m의 2배수 - m의 2배수 

(2) n의 5배수 - n-m의 5배수 - m의 5배수 

 

(1)식과 (2)식의 최소값을 구하면 된다.

 

 

 

#2. 시간초과된 틀린코드

콤비네이션을 활용하여 정석으로 푼 방법이지만, 시간초과가 되었다.

 

def comb(m,n): #콤비네이션 함수 정의
  if n == 0:  #mC0의 값은 1이므로
    return 1
  else:
    o = 1
    for i in range(1, m+1):
      o = i*o
    p = 1
    for i in range(1, m-n+1):
      p = i*p
    q = 1
    for i in range(1, n+1):
      q = i * q
    return o//(p*q)
a,b = map(int, input().split())
z = comb(a,b)  #콤비네이션 구하기

cnt = 0 #0의 개수 세기
for i in str(z)[::-1]:
  if i == '0':
    cnt += 1
  else:
    print(cnt)
    break
print(comb(a,b))

함수 정의는 nCr에서

 n ! / { ( n - r ) !  * r ! }을 구해주고, 그 다음 0의 개수를 세는 방법이다.

위 코드로 작성하면 파이썬을 돌렸을 때는 제대로 돌아가지만, 0의 개수를 구하는 과정에서 for i in str(com(a,b))[::-1]:

str의 방식으로 숫자를 거꾸로 입력하기 위해서는

뒤에서부터 가상의 배열에 집어넣은 뒤 다시 꺼내서 검출하는 방식으로 진행되다 보니 시간초과가 된다.