1676. 팩토리얼 0의 개수 (파이썬)

문제

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

입력

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

출력

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

 

최종 답:

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

 

문제풀이:

sol1)

10! = 3628800 이라서 이 경우 뒤에서부터 센 0의 개수는 2개이다. 

25!=15,511,210,043,330,985,984,000,000 의 경우 0의 개수는 6개이다. (중간의 0은 세지 않는다)

이런 결과가 어떻게 나오는 것일까?

 

10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

 

에서 10은 총 2번 곱해진다. 따라서 답이 2가 된다. 그렇다면 10은 2와 5의 곱으로 이루어져 있으므로, 10! 2와 5의 지수를 각각 구해 더 작은 수를 구하면 된다. 그러나 직관적으로 봤을 때 2의 배수보다 5의 배수가 훨씬 많으므로, 5의 배수만 세어 주면 된다. 

 

10!의 경우 5가 곱해지는 횟수는 10//5=2이다.

그런데 25!의 경우 25//5=5인데 답은 6이다. 왜 그럴까? 이는 25 x 24 x ...x 1 중에서 25가 5의 제곱이므로 5가 한번 더 곱해졌기 때문이다. 즉, 25, 50, 75, 100 일 때 0의 개수가 늘어난다. 마찬가지로 125, 250, 375, 500일때도 0의 개수가 하나씩 늘어난다. 그런데 문제에서 N은 500보다 작거나 같다고 했으므로 625 (5^4) 이상의 경우는 생각하지 않는다.

 

sol2) 

import math as m

N = int(input())
M=m.factorial(N)

M_lst=list(str(M))
M_lst=list(reversed(M_lst))

for i in range(len(M_lst)):
     if M_lst[i]=='0':
         cnt+=1
     else:
         print(cnt)
         break

 

N!을 구하는 라이브러리를 이용해서 풀어도 정답처리가 된다.

math.factorial()

그리고 이 값을 list로 바꿔주고, 리스트의 순서를 뒤집어서 앞에서부터 0의 개수를 세어 주면 된다.

 

👉 reverse()와 reversed() 의 차이
reverse는 list 타입에서 제공하는 함수이고, 값을 반환하지 않고, 단순히 해당 list를 뒤집어준다.
reversed는 내장함수이고, reversed 객체를 반환하긴 하지만, list혹은 tuple로 적절히 형변환하여 사용해야 한다.

 

출처: https://itholic.github.io/python-reverse-reversed/

 

troubleshooting

처음엔 팩토리얼을 for 반복문을 활용해서 구현했다. 그런데 백준에서 정답 처리가 되지 않는다. 왜냐하면 N이 클 경우 overflow가 발생하기 때문이다. 팩토리얼 속에 있는 5의 배수의 개수를 활용해서 풀어야 한다.

 

*완성된 코드는 깃허브에 올려두었습니다