1676번: 팩토리얼 0의 개수

문제 설명

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

제한 사항

• 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)
• 첫째 줄에 구한 0의 개수를 출력한다.

문제 풀이 1

처음 문제를 보고 든 생각은 dp 였다. n의 수가 크기 때문에 팩토리얼 값을 구하고 문자열 처리를 통해서 뒤에서 0의 개수를 카운트하려는 생각을 했다. 그러나 runtime error 생각해보니 50!의 자릿수는 65자리 500!은 1135자리라는 경이로운 숫자라는 사실을 간과하고 코드를 작성했다.

python에서는 객체형태의 껍데기가 int를 감싸고 있는 구조라서 저런 자리수의 숫자도 저장할 수는 있지만 주어진 문제의 메모리제한쯤은 가볍게 넘겨버리지 않을 까 조심스레 예상해본다.

n = int(input())

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

res = 0
for i in str(dp[n])[::-1]:
    if i != '0':
        break
    res += 1
print(res)

문제풀이 2

그래서 수학적 사실을 약간 이용하기로 했다 문제에서 0의 갯수를 세라는 뜻은 팩토리얼 계산 후에 10의 n승이 몇번 곱해져있는지를 세라는 것과 같으니 주어진 n에 따라 2와 5의 약분을 통해 전체 수에 곱해지는 2와 5의 개수를 구해 10이 곱해진 횟루를 return 하도록 했다.

n = int(input())

two = 0
five = 0
for i in range(1, n + 1): // n!= n*n-1*n-2...*2*1
    temp = i
    while temp % 2 == 0 or temp % 5 == 0:
        if temp % 2 == 0:
            temp = temp // 2
            two += 1
        if temp % 5 == 0:
            temp = temp // 5
            five += 1
print(min(two, five))