combinationzero

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 문제의 크기가 1,000,000 이므로 1,000,000 팩토리얼을 연산할 수 없을 뿐더러 저장할 수 있는 수 자료형도 없음
2. 따라서, 다른 시선으로 접근을 해야함
3. 끝자리 0의 개수는 10의 거듭제곱 즉, 2와 5의 곱으로 이루어져 있기 때문에 n 과 m에 대하여 2와 5로 각각 몫이 1이 될 때 까지 나누면서 2와 5의 개수를 저장함
4. 마찬가지로, Combination의 공식에 의해 m과 n-m에 대해서도 2와 5의 개수를 저장함
5. 2와 5의 곱셈으로 이루어져 있고, Combination 공식에 의해 n의 2의 개수 및 5의 개수에서 m과 n-m의 2의 개수 및 5의 개수를 제외시켜줌
6. 10은 2와 5의 짝이 맞아야 하므로 최종적으로 구한 2와 5의 개수중 더 작은 값을 구함으로써 문제를 해결함

5. 전체 코드

//
//  main.swift
//  CombinationZero
//
//  Created by 이영재 on 2022/03/08.
//MARK: - combinationzero

//MARK: - Framework
import Foundation

//MARK: - Function
func getNumberTwoCount(_ number: Int) -> Int {
    var numberTwo = 2
    var count: Int = 0
    
    while numberTwo <= number {
        count += number / numberTwo
        numberTwo *= 2
    }
    
    return count
}

func getNumberFiveCount(_ number: Int) -> Int {
    var numberFive: Int = 5
    var count: Int = 0
    
    while numberFive <= number {
        count += number / numberFive
        numberFive *= 5
    }
    
    return count
}

func solution() -> Void {
    //MARK: - Input
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    let n: Int = input.map { Int($0) }[0] ?? 0
    let m: Int = input.map { Int($0) }[1] ?? 0
    var answer: Int = 0
    var numberTwoCountN: Int = 0
    var numberFiveCountN: Int = 0
    var numberTwoCountM: Int = 0
    var numberFiveCountM: Int = 0
    var numberTwoCountNM: Int = 0
    var numberFiveCountNM: Int = 0
    var numberTwoCount: Int = 0
    var numberFiveCount: Int = 0
    
    //MARK: - Process
    numberTwoCountN = getNumberTwoCount(n)
    numberFiveCountN = getNumberFiveCount(n)
    numberTwoCountM = getNumberTwoCount(m)
    numberFiveCountM = getNumberFiveCount(m)
    numberTwoCountNM = getNumberTwoCount(n - m)
    numberFiveCountNM = getNumberFiveCount(n - m)
    
    numberTwoCount = numberTwoCountN - numberTwoCountM - numberTwoCountNM
    numberFiveCount = numberFiveCountN - numberFiveCountM - numberFiveCountNM
    answer = numberTwoCount > numberFiveCount ? numberFiveCount : numberTwoCount
    
    //MARK: - Output
    print(answer)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.