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

풀이 아이디어

사실상 수학문제입니다.
문제의 설명을 보면 풀이하는데에 전혀 어려움이 없어보이지만,
10 팩토리얼만 해도 3,628,800 입니다. 문제에서 입력값은 500까지 들어올 수 있고 팩토리얼을 직접 구하게 되면 수가 너무 커져서 overflow가 발생하여 오답처리가 됩니다.
팩토리얼에서 끝에 오는 0의 개수는 숫자에 포함된 2와 5의 쌍에 의해 결정됩니다.
2는 2,4,6 .. 등에서 충분히 많으므로 사실상 5의 개수만 세면 됩니다.

예를 들어 10! = 109*..54321 에서 5와 10이 두개의 0을 생성합니다
따라서 n! 의 끝에오는 0의 개수는 n 이하의 숫자 중 5의 배수들의 개수를 세는 것으로 구할 수 있습니다.

풀이

let input = Int(readLine()!)!

if input >= 1 {
    var result = 0
    var divisor = 5

    while input / divisor > 0 {
        result += input / divisor
        divisor *= 5
    }

    print(result)
} else if input == 0 {
    print(0)
}