[실버 IV] 1676번. 팩토리얼 0의 개수

 문제 

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

1676번: 팩토리얼 0의 개수

 사용 언어 

Python3

 풀이 과정 

 실버 IV 지만 그래도 아이디어가 한 번에 맞아서 기분 좋은!!

 

팩토리얼 연산을 했을 때 맨 뒤에 붙는 0의 개수를 구하는 문제였다.

0은 곧 10을 곱한 것을 의미하니 2*5의 세트 개수를 구하면 된다고 생각했고, 따라서 처음에는 2의 개수 5의 개수를 각각 구해서 min값을 저장하려 했다.

 

그런데 풀다 보니 5가 한 번 나올 동안 2는 무조건 한 번 이상 나온다는 것을 깨달았고, 따라서 새로 더할 숫자가 5로 나누어 떨어지는 개수만 구해서 dp로 저장해주었더니 맞았습니다!!

나는 이 아이디어도 괜찮았다고 생각했는데  맞힌 사람 의 풀이를 보니 dp를 사용하지 않고 수학적으로 푸는 방법이 있었다. 그 방법은 너무 간단하지만 아래에 기록하겠다!

 제출 답안 

from sys import stdin

N = int(stdin.readline())

dp = [0 for _ in range(N+1)]
for i in range(2, N+1):
    # 2는 진짜 엄청 많음, 5가 있어야 함
    five = 0
    cur = i
    while cur % 5 == 0:
        five += 1
        cur //= 5
    dp[i] = dp[i-1] + five

print(dp[-1])

 다른 사람 코드 

수학적으로 풀면 아아아주 간단하게 다음과 같이 풀 수 있다. 똑같이 5의 개수만 고려한다는 것은 똑같은데 N이 최대 500까지이므로 5, 25, 125를 나눈 몫을 더하면 답이 되는... 다들 진짜 똑똑이다. 이런 생각은 어떻게 하는지😦

a = int(input())
print(a//5 + a//25 + a//125)

➡ 메모리도 똑같고 시간도 별로 차이 안나서 사실 좀 놀랐다. for문 안에 while문까지 써서 내 코드가 훨씬 오래걸릴 줄 알았는데 범위가 작아서 그런가보다.