2004번 '조합 0의 개수'

import java.io.*;

import java.util.*;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

String[] input = in.readLine().split(" ");

final int n = Integer.parseInt(input[0]);

final int m = Integer.parseInt(input[1]);

final int nMinusM = n - m;

int countOfBoonzaTwo = 0;

int countOfBoonzaFive = 0;

int countOfBoonmoTwo = 0;

int countOfBoonmoFive = 0;

long powerTwo = 2;

long powerFive = 5;

while(powerTwo <= n) {

countOfBoonzaTwo += (n / powerTwo);

powerTwo *= 2;

}

while(powerFive <= n) {

countOfBoonzaFive += (n / powerFive);

powerFive *= 5;

}

powerTwo = 2;

powerFive = 5;

while(powerTwo <= m) {

countOfBoonmoTwo += (m / powerTwo);

powerTwo *= 2;

}

while(powerFive <= m) {

countOfBoonmoFive += (m / powerFive);

powerFive *= 5;

}

powerTwo = 2;

powerFive = 5;

while(powerTwo <= nMinusM) {

countOfBoonmoTwo += (nMinusM / powerTwo);

powerTwo *= 2;

}

while(powerFive <= nMinusM) {

countOfBoonmoFive += (nMinusM / powerFive);

powerFive *= 5;

}

int twoResult = countOfBoonzaTwo - countOfBoonmoTwo;

int fiveResult = countOfBoonzaFive - countOfBoonmoFive;

System.out.println(twoResult < fiveResult ? twoResult : fiveResult);

}

}

이 문제를 아래의 팩토리얼 0의 개수 처럼 풀었다가는 입력 범위 때문에 시간 초과가 난다..

n팩토리얼에서 특정 인수 m의 개수를 세기 위해

n/m의 개수, n/m^2의 개수... 이렇게 구해가며 더해주었다.

let input = readLine()!.split(separator: " ").map { Int($0)! }

let n = input.first!

let m = input.last!

let nMinusM = n - m

var countOfBoonzaTwo = 0

var countOfBoonzaFive = 0

var countOfBoonmoTwo = 0

var countOfBoonmoFive = 0

func solve(_ first: inout Int, _ second: inout Int, _ value: Int) {

    var powerTwo = 2

    var powerFive = 5

    while powerTwo <= value {

        first += (value / powerTwo)

        powerTwo *= 2

    }

    while powerFive <= value {

        second += (value / powerFive)

        powerFive *= 5

    }

}

solve(&countOfBoonzaTwo, &countOfBoonzaFive, n)

solve(&countOfBoonmoTwo, &countOfBoonmoFive, m)

solve(&countOfBoonmoTwo, &countOfBoonmoFive, nMinusM)

let twoResult = countOfBoonzaTwo - countOfBoonmoTwo

let fiveResult = countOfBoonzaFive - countOfBoonmoFive

print(twoResult < fiveResult ? twoResult : fiveResult)