[백준 - python] 2004번: 조합 0의 개수

문제 링크

2004번: 조합 0의 개수

문제 풀이

def countNum(target, num):
  cnt = 0 
  while target > 0:
    target //= num
    cnt += target
  return cnt


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

count_two = countNum(n, 2) - countNum(k, 2) - countNum(n - k, 2)
count_five = countNum(n, 5) - countNum(k, 5) - countNum(n - k, 5)

print(min(count_two, count_five))

2004 입출력 예시

*key point:

n! = 2^a x 5^b x m의 a, b 중 작은 값 만큼 뒤에서부터 0이 존재함을 이용한다.

 

25!을 예로들어보면,

25! = 25 x 24 x ... x 2 x 1

      = 24 x 22 x ... x 4 x 2 x m  (m은 2의 배수가 아닌 것들)

      = 2^12 x (12 x 10 x 8 x 6 x 4 x 2) x m

      = 2^(12 + 6) x (6 x 4 x 2) x m

      ...

      = 2^(12 + 6 +  3 + 1) x m

같은 방식으로

25!  = 25 x 20 x 15 x 10 x 5 x m  (m은 5의 배수가 아닌 것들)

       = 5^(5 + 1) x m

이 경우

12 + 6 + 3 + 1 = 22

5 + 1 = 6

이므로 두 가지 중 작은 값인 6이 답이 된다.

 

2, 5의 지수가 갖는 규칙은 (최대값/자신) 에서부터 (자신)을 나눈 수를 계속 더하는 것이므로 이를 반복문으로 구현한다.

 

 

*comment: 스스로 해결하지 못했다. 단순하게 풀 경우 시간초과가 쉽게 발생하는 문제이기 때문에 시간을 확실히 줄일 수 있는 아이디어가 중요하다.