[백준] 3474 - 교수가 된 현우(Python)
알고리즘
수학
풀이
수의 범위가 (1 <= N <= 십억) 이므로 팩토리얼을 직접 구할 수는 없다.
끝에 0이 몇 개인지 구하는 것은 인수로 10을 몇 개 포함하고 있는지 구하는 것과 같다.
예를 들어 900은 9 x 10 x 10 이므로 끝에 0이 2개이다.
하지만 팩토리얼을 직접 구할 수는 없기 때문에 소인수분해를 이용해야 한다.
10은 5와 2를 인수로 가진다. 따라서 N! 을 구하려면 몇개의 (5 x 2)가 들어있는지 구하면 된다.
정리하면 다음과 같다.
- 어떤 수의 끝에 0이 있다는 건 10 x N 과 같다.
- 10을 만들 수 있는 수는 5와 2뿐이다.
예를 들어 50! 의 끝에 0이 몇개인지 구하려고 한다.
방법은 두가지다
- 50! 에서 2의 배수의 개수를 구하거나
- 5의 배수의 개수를 구하거나
둘 중에 5가 더 크므로 5를 사용하는 것이 더 편리하다.
위에서 5의 배수를 정리하면 다음과 같다.
(5x1), (5x2), (5x3), (5x4), (5x5)
(5x6), (5x7), (5x8), (5x9), (5x10)
마지막의 (5x10)
은 (5x5x2)
와 같다.
위에서 알 수 있는 것은 다음과 같다.
50! 을 소인수분해하면 5로 12번 나눌 수 있다.
따라서 뒤에 0이 12개 붙는다.
위의 계산을 편하게 하려면 5의 배수를 구하고 5x5의 배수를 구하고 5x5x5 ... 를 구하고 그 총합을 합치면 된다. 아래는 그것을 구현한 코드이다.
코드
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
n = int(input()) # 수 입력 받기
count = 0
i = 5
while i <= n:
count += n // i # 5의 배수의 합을 구한다
i *= 5
print(count)
Author And Source
이 문제에 관하여([백준] 3474 - 교수가 된 현우(Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ice-prince/백준-3474-교수가-된-현우Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)