10872번 팩토리얼

문제

링크 : https://www.acmicpc.net/problem/10872

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(factorial(n));
    }

    static int factorial(int n) {
        if(n == 0) {
            return 1;
        } else if(n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

재귀함수를 이용하여서 풀었다.

결과

1676번 팩토리얼 0의 개수

문제

링크 : https://www.acmicpc.net/problem/1676

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for(int i = 5; i <= n; i *= 5) {
            count += n / i;
        }
        System.out.println(count);
    }
}

n을 5, 5의제곱, 5의 세제곱... 순으로 나눈 값을 더해주면 n!에 존재하는 5의 개수가 구해지고 0은 2x5로 만들어지는 것을 이용해서 2의 개수보다 5의 개수가 더 작기 때문에 5의 개수를 구하면 0의 개수를 구한 것과 같아진다.

결과

백준 2004번 조합 0의 개수

문제

링크 : https://www.acmicpc.net/problem/2004

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int two = 0;
        for(int i = 2; i <= n; i *= 2) {
            two += n / i;
        }
        for(int i = 2; i <= m; i *= 2) {
            two -= m / i;
        }
        for(int i = 2; i <= (n - m); i *= 2) {
            two -= (n - m) / i;
        }
        
        int five = 0;
        for(int i = 5; i <= n; i *= 5) {
            five += n / i;
        }
        for(int i = 5; i <= m; i *= 5) {
            five -= m / i;
        }
        for(int i = 5; i <= (n - m); i *= 5) {
            five -= (n - m) / i;
        }
        
        System.out.println(Math.min(two, five));
    }
}

조합 공식에서 0의 개수를 구하기 위해서는
먼저 n!에서 2의 개수를 구하여 two 변수에 더한다. 그런 다음 m!에서 구한 2의 개수를 two 변수에 빼준다. 마지막으로 (n-m)!에서 구한 2의 개수를 two 변수에 빼준다. 그렇게 되면 조합 nCm에서의 2의 개수가 구해진다.
다음은 n!에서 5의 개수를 구하여 five 변수에 더한다. 그런 다음 m!에서 구한 5의 개수를 five 변수에 빼준다. 마지막으로(n-m)!에서 구한 5의 개수를 five 변수에 빼준다. 그렇게 되면 조합 nCm에서의 5의 개수가 구해진다.
이제 이 two와 five 변수 중에서 더 작은 수를 출력하면 이게 바로 nCm에서의 0의 개수가 된다.
🚨🚨 int형으로 풀게 되면 런타임 에러(by zero)가 일어나기 때문에 long형으로 풀어야 한다.

결과