BOJ 1676. 팩토리얼 0의 개수

BOJ 1676. 팩토리얼 0의 개수

풀이

0의 개수는 10을 의미하고 10은 2*5로 나타낼 수 있다.
팩토리얼을 소인수 분해하여 2의 개수 5의 개수를 구한다.

Java

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int countOfTwo = 0;
        int countOfFive = 0;
        for (int i = 1; i <= n; i++) {
            int target = i;
            while (target % 2 == 0) {
                countOfTwo++;
                target /= 2;
            }

            while (target % 5 == 0) {
                countOfFive++;
                target /= 5;
            }
        }

        System.out.println(Math.min(countOfTwo, countOfFive));
        sc.close();
    }
}

여기서 2는 무조건 5보다 많으므로 
5의 배수 개수만 구하는 방법도 존재한다

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        s.close();
        int count = 0;
        while (n >= 5) {
            count += n / 5;
            n /= 5;
        }
        System.out.println(count);
    }
}

Kotlin

fun main() {
    val num = readLine()!!.toInt()
    println(num / 5 + num / 25 + num / 125)
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/1676.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/1676.kt