백준 2004번 파이썬

이문제가 정수,조합론의 마지막 문제이다 이것으로 이단계는 마무리되었군요 뿌듯하네요!

문제자체는 바로전문제인 팩토리얼의 0의개수와 매우유사한데 거기서 이항계수 개념만 추가된문제라 쉽게 구현할수있었습니다

def 팩토리얼(num):
    ans=1
    for i in range(1,num+1):
        ans=ans*i
    return ans

def 이항계수(n,k):
    if k < 0:
        return 0
    elif k > n:
        return 0
    else:
        return 팩토리얼(n)//(팩토리얼(k) * 팩토리얼(n-k))

n,k=map(int,input().split())
num=이항계수( n, k  )
count=0
for i in range(len(str(num))-1,-1,-1):
    if str(num)[i]=='0':
        count+=1
    else: 
        break
print(count)

이항계수를 구한뒤 맨 아래서부터 0의 개수를 세는 정말 직관적인 프로그램입니다

다만 이게 시간초과가 났습니다 이유를 살펴보니

바로 전 문제는 최대 500!까지였었는데 이번문제는 최대20억!까지입니다

20억팩토리얼을 계산하기위해서는 반복문이 20억번 돌아가야합니다 얼마나 큰수가 나올지는 사실 감도 안잡히는 수준이죠

따라서 팩토리얼을 직접구하지않고 답을 찾아야한다는 생각에 이르렀습니다

 

힌트를 얻기위해 문제가 모여있는 페이지를 보니 소인수분해의 성질을 이용하여 푸는 문제라고 작은 설명이 되있더군요 

이러한 성질을 이용해 N!일때 1에서 N까지의 숫자중 5의 개수와 뒤에 붙는 0의 개수가 같다는걸 알게되었습니다

5와 2가 있으면 10이되는데 어차피 2의 개수는 5보다 훨신 많으니 5의 개수만 보면 되는것입니다

제가 말을 잘못해서... 코드로 한번 보시죠!

def 영계산기(num):
    exponent=1
    ans=0
    while num >= 5**exponent:
        ans+=num//5**exponent
        exponent+=1

    return ans

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

print(영계산기(n)-영계산기(n-m)-영계산기(m))

이항계수 부분은 영계산기(n)-영계산기(n-m)-영계산기(m)으로 구현을 했습니다

근데 틀렸습니다.. 왜 틀린지를 몰라서 질문계시판을 보다가 반례를 찾아내었습니다

바로 5, 4입니다 답은 0인데 출력은 1로 됩니다

5가 있는것은 사실이지만 2가없어서 0이 안붙는것입니다 이부분을 개선해서제출한 코드는 아래와같습니다

def 오계산기(num):
    exponent=1
    ans=0
    while num >= (5**exponent):
        ans+=num//(5**exponent)
        exponent+=1
    return ans

def 이계산기(num):
    exponent=1
    ans=0
    while num >= (2**exponent):
        ans+=num//(2**exponent)
        exponent+=1
    return ans

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

print(min(오계산기(n)-오계산기(n-m)-오계산기(m),이계산기(n)-이계산기(n-m)-이계산기(m)))

오계산기와 이계산기 함수명에 숫자못쓰는거 불편하다

이항계수결과의 2소인수분해결과와 5소인수분해의결과의 min값이 바로 10의 값이다 정답처리되었다

이번문제는 꽤 어려웠는데 그래도 답을 찾아보지않고 나름 창의적인 방법을 찾아낸것같아서 뿌듯했다

ps.머리속으로 생각해내는것은 참쉬운데 이것을 말로 남들에게 내 생각을 설명하는건 정말 어려운것같다

블로그글을 작성 하면서 이부분의 능력이 향상되길바란다