[알고리즘][백준] 2004번 조합 0의 개수 - 파이썬(python) 풀이

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

---

1676번 팩토리얼 0의 개수와 똑같이 5의 개수를 구하면 되겠다고 생각했는데...

import sys

n, m = map(int, sys.stdin.readline().split())

# 25!

# (25-12)! 12!

a = n - m

cnt = 0

for i in range(1, 14):

    cnt += n // (5 ** i)

    cnt -= a // (5 ** i)

    cnt -= m // (5 ** i)

print(cnt)

틀렸다고....

 

알아보니 10 = 2 * 5라서 2의 개수가 5의 개수보다 작은 경우를 고려해야한다고...!

 

조합의 경우 n! / ((n-m)! * m!) 이런 형태라 2의 개수가 작은 경우도 생기는 것인가...?

 

그렇게 짜본 나의 코드

import sys

n, m = map(int, sys.stdin.readline().split())

# 25!

# (25-12)! 12!

a = n - m

five_cnt = 0

two_cnt = 0

for i in range(1, 14):

    five_cnt += n // (5 ** i)

    five_cnt -= a // (5 ** i)

    five_cnt -= m // (5 ** i)

for i in range(1, 31):

    two_cnt += n // (2 ** i)

    two_cnt -= a // (2 ** i)

    two_cnt -= m // (2 ** i)

print(min(five_cnt,two_cnt))

 

나처럼 5 ** 13, 2**30 이렇게 직접 2,000,000,000 넘는지 계산하지 않고 푸는 방법도 있다!

import sys

n, m = map(int, sys.stdin.readline().split())

# 25!

# (25-12)! 12!

def sol(n, k):

    cnt = 0

    while n > 1:

        n //= k

        cnt += n

    return cnt

five_cnt = sol(n, 5) - sol(n-m, 5) - sol(m, 5)

two_cnt = sol(n, 2) - sol(n-m, 2) - sol(m, 2)

print(min(five_cnt,two_cnt))

 

메모리랑 시간은 동일하게 나오긴 하다!

 

 

2004_조합0의개수.py

0.00MB