[단계별로 풀어보기] 정수론 및 조합론 - 조합 0의 개수 (2004)

2004번: 조합 0의 개수 (acmicpc.net)

2004번: 조합 0의 개수

시도 1

실제 factorial을 이용하여 풀어보기

import math

n, m = map(int, input().split())

nf = math.factorial(n)
mf = math.factorial(m)
nmf = math.factorial(n-m)

e = str(nf // (mf*nmf))

cnt = 0
for i in range(len(e)-1, -1, -1):
    if e[i] == '0':
        cnt += 1
    else:
        break
print(cnt)

시간 초과로 실패했다.

값으로 주어질 수 있는 숫자가 너무 크기 때문에 실패한 모양.

 

시도 2

Pascal의 삼각형을 이용해서 풀어보려고 했다.

출처 - 위키피디아 이항계수

n, m = map(int, input().split())

ar1 = [1] + [0]*n
ar2 = [1] + [0]*n


for i in range(1, n+1):
    if i % 2 == 1:
        for j in range(0, i):
            ar2[j+1] = ar1[j] + ar1[j+1]
    else:
        for j in range(0, i):
            ar1[j+1] = ar2[j] + ar2[j+1]

if n % 2 == 1:
    num = str(ar2[m])
else:
    num = str(ar1[m])

cnt = 0
for i in range(-1, -len(num)-1, -1):
    if num[i] == '0':
        cnt += 1
    else:
        break
print(cnt)

메모리 초과로 실패했다.

 

시도 3

0의 개수를 구하는 것이니 2와 5의 개수를 알아내면 된다.

n의 팩토리얼에서 어떤 숫자 num이 몇개 들어가는지를 알아내는 알고리즘은 다음과 같다.

def count(n, num):
    cnt = 0
    while n != 0:
        n = n // num
        cnt += n
    return cnt

이를 이용하면 간단하게 답을 알아낼 수 있다.

def count(n, num):
    cnt = 0
    while n != 0:
        n = n // num
        cnt += n
    return cnt

n, m = map(int, input().split())

t = count(n, 2) - count(m, 2) - count(n-m, 2)
f = count(n, 5) - count(m, 5) - count(n-m, 5)

print(min(t,f))