백준 파이썬 2004 조합 0의 개수

 

🚀접근하기

원래 팩토리얼을 구하는 것처럼 구하면 메모리 초과가 일어나서 다른 방법으로 풀어야했던 문제.

끝자리 0의 개수를 구하는 것인데, 끝자리가 0이되려면 a * 10^n 으로 표현이 돼야하고, 10은 2*5로 소인수 분해된다는 것을 생각하면 쉽게 풀리는 문제이다!

2와 5가 쌍을 이루어야 끝자리가 0이 될 수 있기 때문에(2가 아무리 많아도 5가 적으면 0의 개수는 5의 개수), 2와 5중 더 작은 개수를 가진 것을 출력해주면 된다.

🎉코드

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

def two(num):
    two_cnt = 0
    n=1
    i=2
    while n != 0:
        n = num // i
        two_cnt += n
        i = i * 2
    return two_cnt

def five(num):
    five_cnt = 0
    n=1
    i=5
    while n != 0:
        n = num // i
        five_cnt += n
        i = i * 5
    return five_cnt

a = two(n) - two(m) - two(n-m)
b = five(n) - five(m) - five(n-m)

print(min(a,b))

 

 

2의 개수를 구하는 함수를 예로 들어서,

만약 num이 25라면

25 // 2 = 12

25 // 4 = 6

25 // 8 = 3

25 // 16 = 1

 

12 + 6 + 3 + 1 = 22

25의 2의 개수는 22개이다.

 

5의 개수를 구하는 함수도 위와 같은 방식으로 만들어주면 된다.

 

마지막엔 n의 2의개수 - m의 2의개수 - n-m의 2의개수를 구해주면 된다.

 

a,b중 min 값을 구하는 이유는 위에도 언급했듯이 2와 5가 쌍을 이루어야만 끝자리가 0이 될 수 있기 때문에 더 작은 것, 즉 쌍을 이루는 개수를 구하기 위함이다.

💪다짐

팩토리알 문제였지만 팩토리알은 쓰이지 않았던.. 아예 다른 방식으로 풀어야 했던 문제.

팩토리알에서 0의 개수 구하는 방법을 잊지 말아야겠다.