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

www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

메모리 초과, 시간 초과.. 난리가 났던 문제다 ㅎㅎ

메모리 초과를 해결하면 시간초과가 나고~~~~~아이고야

 

마지막으로 생각해낸건, 조합을 구한 후에 0을 찾는 것이 아닌,

0이 어떻게 생겨나는지 생각해보았다

바로 2,5의 개수를 세고, 2와 5의 개수중에 작은 수를 택하면된다

 

오답노트를 작성하자면..

 

#메모리초과

#메모리 초과

from itertools import combinations

#팩토리얼 구하기
def func(n):
    if n==0:
        return 1
    else:
        result=1
        for i in range(1,n+1):
            result=result*i

        return result
        
n,r=map(int,input().split())

k=len(list(combinations([i for i in range(1,n+1)],r)))
k=str(k)
cnt=0
for i in range(len(k)-1,-1,-1):
    if k[i] =='0':
        cnt+=1
    else:
        break
        
print(cnt)

#시간초과

#시간 초과

import sys

#팩토리얼 구하기
def func(n):
    if n==0:
        return 1
    else:
        result=1
        for i in range(1,n+1):
            result=result*i

        return result
        
n,r=map(int,sys.stdin.readline().split())

a=func(n)
b=func(r)
c=func(n-r)

k=a//(b*c)

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

#성공!!!

 

#2와 5의 개수만 세기
#깨달음...

import sys

n,r=map(int,sys.stdin.readline().split())
def check_2(n):
    cnt=0
    while n!=0:
        n=n//2
        cnt+=n
    return cnt
            
            

def check_5(n):
    cnt=0
    while n!=0:
        n=n//5
        cnt+=n
    return cnt

print(min(check_2(n)-check_2(n-r)-check_2(r),check_5(n)-check_5(n-r)-check_5(r)))