[Python]백준 BaekJoon.AC 1676 : 팩토리얼 0의 개수(for문, while문)

 

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

1676번: 팩토리얼 0의 개수

 

 

 

문제 자체는 단순한데 고민을 많이 했다.

함수나 더 복잡한 연산을 요하는 줄 알았는데, 통과한 코드를 보면 썩 그렇지도 않았다.

 

 

 

2와 5가 핵심이란 사실은 쉽게 눈치챌 수 있었다. 0이란 숫자는 2와 5를 곱해서만 만들어지니까.

문제는 이걸 어떻게 구워 삶느냐인데, 

1부터 N까지 루프를 돌며 각 숫자에 2와 5가 몇 번 곱해져있는지 구하고 싶었다.

 

 

그러기 위해선 그 숫자를 2와 5로 나눠줘야 했고,

while문과 if문을 통해 해당 수(2 or 5)로 나누어 떨어지는지 확인한 후 count해줬다.

 

 

2와 5 모두 하나씩은 있어야 10이 만들어지니,

2의 개수와 5의 개수 중 작은 수를 정답으로 골랐다.

사실 2는 너무 흔한? 숫자여서 대개 5의 개수가 정답일 테다. (그냥 5의 개수가 정답이라 봐도 된다..) 

 

 

제출 후 다른 사람들의 코드를 살폈는데, 원리는 비슷하나 더 간략하게 추려낸 코드들이 많았다.

그냥 5, 25, 125로 나눈 몫을 다 더해준다던지..(2는 볼 가치가 없다.. 무조건 5보다 개수가 많으니..)

아이디어를 참고할 가치가 있었다. 정말 다양한 방법이 있었고, 다들 2는 취급해주지 않았다ㅋㅋㅋ

 

 

 

N = int(input())

count2 = 0
count5 = 0
for n in range(1, N+1):
    while True:
        if n % 2 == 0:
            n = n / 2
            count2 = count2 + 1
        else:
            break

    while True:
        if n % 5 == 0:
            n = n / 5
            count5 = count5 + 1
        else:
            break

print(min(count2, count5))

 

 

실제 위 코드에서 2를 생각해주지 않아도 정답처리 된다.

 

<참고 코드>

N = int(input())

count5 = 0
for n in range(1, N+1):

    while True:
        if n % 5 == 0:
            n = n / 5
            count5 = count5 + 1
        else:
            break

print(count5)