백준 1676번 팩토리얼 0의 개수 - 스위프트(Swift) 풀이

 수학 문제.

1. 뒤에 붙는 0의 개수는 10이 몇 번 곱해졌는지와 같다.
2. 10을 소인수분해하면 10 = 2 X 5이다.
2. 따라서 N! 을 소인수분해했을 때 min(2의 개수, 5의 개수)가 맨 뒤에 붙는 0의 개수이다. 
3. 2의 개수가 5의 개수보다 많을 테니, 5의 개수를 세준다.

---

1.  뒤에 붙는 0의 개수는 10이 몇 번 곱해졌는지와 같다.

 어떤 수의 뒤에 0이 붙으려면 10을 곱해야 한다. 따라서 N! 을 계산할 때 10이 몇 번 곱해졌는지를 세면 된다.

 

1.  10을 소인수분해하면 10 = 2 X 5이다.

 10을 소인수분해하면 2 X 5이다. 따라서 어떤 수에 10을 곱한다는 말은 2와 5를 모두 한 번씩 곱해준다는 말이다.

 

2. 따라서 N!을 소인수분해했을 때 min(2의 개수, 5의 개수)가 맨 뒤에 붙는 0의 개수이다.

 2와 5를 모두 한 번씩 곱해주어야 하므로, min(2의 개수, 5의 개수)만큼 10이 만들어질 것이다.

 

3. 2의 개수가 5의 개수보다 많을 테니, 5의 개수를 세준다.

 2는 짝수마다 계속 나온다. 당연히 5의 개수가 더 적을 테니, 5의 개수를 세주면 된다. 곱해진 5의 개수는 (5의 배수의 개수) + 95^2의 배수의 개수) + (5^3의 배수의 개수) + ... 이렇게 세주면 된다. 그런데 어차피 N ≤ 500이므로 5^3 = 125의 배수까지만 세주면 되기 때문에 그냥 하드코딩해줬다.

 

---

let N = Int(readLine()!)!
print(N / 5 + N / 25 + N / 125) // 5의 개수 세기