[python/파이썬] 백준 2004 조합 0의 개수

[문제 출처]

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

2004번: 조합 0의 개수

 

[비슷한 문제 - 백준 1676 ]

https://sodehdt-ldkt.tistory.com/195

[python/파이썬] 백준 1676 팩토리얼 0의 개수

 

[소스 코드1 - 런타임 에러(RecursionError)]

1676번 문제와 다른 점은 팩토리얼에서 조합으로 바뀌었다는 점이다. 

하지만 조합도 결국에는 팩토리얼 연산을 사용하기 때문에 동일한 방법으로 풀었으나, 

런타임 에러가 떴다.

범위가 500이었던 1676번 문제와 달리 2,000,000,000이나 되는데 이 점을 생각하지 못했다.

#2004

def fact(n):
  if n == 0 or n == 1:
    return 1
  else:
    return n * fact(n-1)


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

# //연산자를 사용하지 않으면 결과가 실수형태로 나오기 때문에 
#문자열로 변환했을 때 .이 포함되어 0의 개수를 제대로 셀 수 없음
result = str(fact(n) // (fact(m) * fact(n-m))) 

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

 

[소스 코드2 - 메모리 초과]

RecursionError가 떠서 재귀 함수가 아닌 dp로 풀면 되지 않을까 했는데

역시나 값이 너무 커서 메모리 초과가 떴다.

이때까지도 범위를 생각하지 못했다.

 

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

fact = [1 for _ in range(n+1)]

for i in range(2,n+1):
  fact[i] = fact[i-1] * i

result = str(fact[n] // (fact[m] * fact[n-m]))

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

print(cnt)

 

[소스 코드3 - 맞았습니다!]

 

재귀나 dp가 아니라는 것은 알았으나 어떤 방법으로 풀어야 할지 몰라서 다른 풀이를 찾아봤는데,

전혀 다른 방법으로 접근해야 풀 수 있는 문제였음을 알 수 있었다..

 

어떤 숫자가 0으로 끝난다는 것은 10의 배수가 곱해져 있다는 뜻이며,

10의 배수는 2와 5의 곱으로 이루어져 있다는 점을 이용해서 푸는 문제이다.

 

따라서 2와 5의 개수를 세고 둘 중에서 더 개수가 적은 값을 출력해주면 된다.(짝이 맞지 않는 경우는 10을 이룰 수 없기 때문)

만약 40이라는 숫자가 있을 때

40 = 2 x 2 x 2 x 5로 소인수분해가 가능하다.

2는 3개 5는 1개로 10을 이루는 2와 5는 한쌍만 가능하다.

따라서 더 적은 숫자인 1이 0의 개수가 된다.

 

결론적으로 각 숫자의 2와 5의 개수를 세주는 것이 이 풀이의 핵심이다.

nCr = n!/((n-r)! r!)으로 계산이 가능하고,

지수법칙에 의해

nCr의 2의 개수 = n! 의 2의 개수 - (n-r)! 의 2의 개수 - r! 의 2의 개수로 나타낼 수 있다.

따라서 각각 nCr의 2의 개수와 5의 개수를 세서 더 작은 값을 결과로 출력하면 된다.

#2004

def count2(n):
  cnt = 0
  while n!=0:
    n //= 2
    cnt += n
  return cnt

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

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

result = min(count2(n)-count2(n-m)-count2(m), count5(n)-count5(n-m)-count5(m))
print(result)

 

그런데 처음에 코드를 보고 이해가 되지 않았던 점은 예를 들어 5! 의 5의 개수와 2의 개수를 세야 한다면,

5! 의 값인 120을 소인수 분해해서 2와 5의 개수를 세야 한다고 생각했는데, 

모든 코드들이 함수 인자로 n! 이 아닌 n을 넣어서 이해가 되지 않았었다.

 

그런데 숫자 자체가 아닌 5! 일 때 5개의 숫자가 곱해진다는 점에 주목해서 생각하니 이해가 됐다.

아래는 n=100일 때 5의 개수를 세는 것에 대한 설명이다.