팩토리얼 0의 개수[백준1676] - python

 

정답 코드 먼저 살펴보자

import sys
n = int(sys.stdin.readline())

two_count = 0
five_count = 0

two = 2 
while two <= n :
  two_count += n // two
  two *= 2

five = 5
while five <= n:
  five_count += n // five
  five *= 5

print(min(two_count, five_count))

 

팩토리얼을 수행 했을때 0이 몇개 나오는지 반환하는 문제이다

0을 만들수 있는 조건은 2와 5의 곱이다.

우리는 팩토리얼을 구하는 숫자 범위 안에서 2의 개수와 5의 총개수를 비교해주어야 한다.

 

10을 예로 들어보자

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10

 

2의 등장 개수를 구해야 한다. 근데 4에는 2가 두개 있고 8에는 2가 3개 있다.

이진수로 살펴보자

    1   # 1 
  1*2   # 2 
  3*1   # 3 
  2*2   # 4 
  5*1   # 5 
  3*2   # 6 
  7*1   # 7 
2*2*2   # 8 
  9*1   # 9 
  5*2   # 10

나누어 주는 수를 2씩 곱해주면서 위의 식에서 2를 하나씩 제거해준다는 개념으로 접근했다.

 

2^1에서 1단계의 2들에 접근해 카운팅 해주었고

2^2에서 2단계의 2들에 접근해 카운팅 해주었다

2^3도 마찬가지로 나누어주는 수를 키워주면서 다음 단계의 2에 접근하는식으로 해결하였다.

(머릿속에 있는걸 글로 적으려니까 쉽지 않다. 적은후에 다시 한번 퇴고해봐야겠다)

 

 

문제 : https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수