(JAVA)백준 온라인 2004번 - 조합 0의 개수

맨 처음에 이 문제를 어떻게 접근했었냐면 nCm이라면 n!의 0개수에서 (n-m)!과 m!의 0개수를 빼주면 되는 줄 알았다. 그래서 알고리즘을 어떻게 짰느냐면 전 문제 팩토리얼 0의 개수 문제에서 추가로 작성해서...

import java.util.Scanner;

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

        int n = sc.nextInt();
        int m = sc.nextInt();
        int count1 = 0;
        int count2 = 0;

	for (int i = 5; i <= n; i *= 5) {
            count1 += n / i;
        }

        for (int i = 5; i <= n - m; i *= 5) {
            count2 += (n - m) / i;
        }

        for (int i = 5; i <= m; i *= 5) {
            count2 += m / i;
        }

        System.out.println(count1 - count2);
    }
}

이렇게 짰다 ㅋㅋㅋㅋㅋ 너무 안일한 생각이었다ㅎㅎ

어떻게 접근 하느냐면 2 x 5가 나올 수 있는 소인수 중에서 2의 개수와 5의 개수를 둘다 구한 후에 2와 5 둘 중에 더 적은 수를 출력하면 되는 것이었다! 바로

import java.util.Scanner;

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

        long n = sc.nextLong();
        long m = sc.nextLong();

        long count2 = count(n, 2) - count(n - m, 2) - count(m, 2);
        long count5 = count(n, 5) - count(n - m, 5) - count(m, 5);


        System.out.print(Math.min(count2, count5));
    }

    public static long count(long x, long k) {
        long cnt = 0;
        for (long i = k; i <= x; i *= k) {
            cnt += x / i;
        }
        return cnt;

    }
}

이렇게 ㅋㅋㅋ count메서드를 만들어서 각각 count2, count5에서 n - (n-m) - m을 구한 후 count2와 count5 둘 중에 최솟값을 출력하는 방식으로 하였다. 

하 너무 어렵다