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

1676번: 팩토리얼 0의 개수

시간 제한

 2초

메모리 제한

128MB

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

예제 입력 1 

10

예제 출력 1 

2

예제 입력 2 

3

예제 출력 2 

0

---

나의 풀이

• 마지막 숫자가 0이려면 10이 곱해져야 함
• 따라서 팩토리얼 구성 숫자들을 소인수 분해하여 만들 수 있는 10의 개수를 계산하면 됨

N = int(input())

count_2 = 0
count_5 = 0
for i in range(1, N + 1):
    # 약수로 2, 5를 가지지 않는 경우
    if i % 2 != 0 and i % 5 !=0:
        continue
    # 약수로 5를 가지는 경우 처리
    if i % 5 == 0:
        while i % 5 == 0:
            i //= 5
            count_5 += 1
    # 약수로 2를 가지는 경우 처리
    if i % 2 == 0:
        while i % 2 == 0:
            i //= 2
            count_2 += 1

if count_2 and count_5:
    print(min(count_2, count_5))
else:
    print(0)

---

다른 사람 풀이

• N을 5로 나눈 몫을 가져오면 5를 인수로 가지는 수의 개수를 알 수 있음
• 이때, 5의 제곱 형태의 인수를 가진 수가 있을 수 있기 때문에 while 문으로 반복 시켜준다.

n = int(input())
def five_count(n):
    cnt = 0
    while n != 0:
        n //= 5
        cnt += n
    return cnt
    
print(five_count(n))

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