[BOJ] 백준 1676 팩토리얼 0의 개수 (Swift)

문제

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

1676번: 팩토리얼 0의 개수

풀이

Swift에서 팩토리얼을 직접 계산한다면
최대 500!이라는 큰 수를 기본 자료형인 Int로 나타내기는 어려울 것이다.

다른 방법으로 0의 개수를 구해주어야 한다.

가장 먼저 0이 나타나는 n!은 5이다.
$5! = 5 \times 4\times 3\times 2\times 1 = 120$
$5 \times 2 = 10$ 이므로 0의 개수가 1인것을 확인할 수 있다.

5이후 다음 n도 모두 0이 1개 이상은 있을 것이다.
따라서 n에 대해 $5 \times 2 = 10$가 나오는 횟수를 구해주면 0의 개수를 구할 수 있을 것이다.

2는 짝수에 대해 모두 약수이므로, 2가 나오는 횟수는 따로 고려하지 않고 5의 횟수를 구하면 된다.
10은 그렇다 치고, 100같은 경우는 어떨까?

100! 은 $5 \times 2$의 횟수가 20번 나올 것이다.
$5^2 \times 2^2$ 같은 경우에도 0의 개수를 1번만 체크하게 될 것이다.
따라서 $5^2$의 횟수도 구해주어야 한다.

마찬가지로, $5^3 = 125$의 횟수도 구해주어야 한다.

소스코드

	let n = Int(readLine()!)!
	print(n / 5 + n / 25 + n / 125)

view raw 팩토리얼 0의 개수.swift hosted with ❤ by GitHub

후기

코드만 봤을 때는 엄청 쉬워보일 수 있는 문제
하지만 수학적으로 생각을 해야하는 문제였다.