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

코드 작성

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))

 코드  풀이 (시간초과) 

# 0. 위 코드로 푼 이유 및 틀린 이유

 

인터넷에서 찾아보면 2와 5의 개수를 이용하여 위 문제를 풀던데, 콤비네이션의 계산방법으로 구하는 위 풀이로 작성하는 의도가 맞다고 본다.

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

str의 방식으로 숫자를 거꾸로 입력하기 위해서는 가상의 배열에 뒤에서부터 집어넣은 뒤 다시 꺼내서 검출하는 방식으로 진행되다 보니 시간초과가 나온다.

 

#1. 코드 풀이

문제는 함수를 정의했고, 원래 콤비네이션 푸는 방식으로 적용했다.

우선, mCn은 m!/((m-n)!*n!)으로 나타낼 수 있다.

그리고 m!, (m-n)!, n!를 각각 o, p, q로 정의하여 출력값을 print(o//(p*q))로 하였다.