BOJ 1676 - 팩토리얼 0의 개수 (Python3)

필요한 수학적 배경 지식을 중학생이 간단하게 이해할 수 있으면 브론즈 II에서 브론즈 I 티어를 주는 것이 권장되어 있다.

달리 말하면 알고리즘 짜는 게 아무리 간단하기 그지없더라도 중학생 수준에서 유추하기 어렵다면 실버 수준으로 올라간다는 이야기다.

이게 조금 불합리한 걸 넘어서 난이도 역전 현상의 주범이 되어 있는 건 내 착각일까?

내가 수학적 공대생이라서가 아니라, 이런 문제는 어지간한 브론즈 II보다도 쉬워 보인다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

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

 

입력

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

 

예제 입력)

# 예제 입력 1
10

# 예제 입력 2
3

 

출력

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

 

예제 출력)

# 예제 출력 1
2

# 예제 출력 2
0

 

---

내 코드

def fact0(n):
    c = 0
    while n!=0:
        n//=5
        c+=n
    return c

print(fact0(int(input())))

 

N!의 마지막에 오는 0의 갯수는, \(N!=k\times10^n\,\,(10\not\mid k)\)의 n과 같다.

이 때, a의 p의 최대제곱 x을 \(a=k\timesp^x\,\,(p\not\mid k)\)라고 두면, 이러한 n은 N!의 2의 최대제곱과 N!의 5의 최대제곱 중 더 작은 쪽일 것이다.

왜냐하면 2와 5가 하나하나씩 짝지어 곱해져서 10이 될 것이기 때문에.

그리고 당연히 2 < 5 이니까 N!의 5의 최대제곱이 더 작을 터이다.

 

N!의 5의 최대제곱은 어떻게 구하는가. 그것은 1부터 N까지의 수들 중 5의 배수 갯수 + 25의 배수 갯수 + 125의 배수 갯수 +... 이 될 것이다.

이런 합에서 \(5^n\)은 정확하게 5의 배수 갯수, 25의 배수 갯수, ..., \(5^n\)의 배수 갯수까지 하여 n번 카운트될 것이기 때문.

이제 n을 구하는 방법을 알았으니, 그러한 값을 반환하여 주는 fact0 함수를 만들면 끝이다.

 

이로서 1676번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.