백준 2004 - 조합 0의 개수 JAVA

문제, 입출력, 테스트케이스

해당 문제는 아이디어가 생각날 듯 말 듯해서 누워서 생각하다가 한 10분 잠들었다가 일어났더니 생각나서 풀어버린 문제이다. 가끔 누워서 아이디어를 떠올리다 보면 풀리는 문제가 있다.

 

<문제 접근/풀이과정>
1. nCm = n! / ((n-m)! * m!)이다.
2. 끝자리 0의 갯수는 10이 얼마나 있느냐 = 2 * 5 쌍의 개수
3. 그냥 5의 배수 나열해 보기
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125...
1  1   1  1   2   1   1  1  1   2  1    1  1  1   2  1   1   1   1   2     1    1    1    1     3
-> 5의 개수는 결국 특정 n에서의 5로 나눈 몫 + 5^2(25)로 나눈 몫... + 5^n으로 나눈 몫
고로 n! 이 포함하는 5의 개수는 n이하의 5의 거듭제곱 수로 나눈 몫들의 합이며, 2의 갯수 또한 n이하의 2의 거듭제곱 수로 나눈 몫들의 합이다.
됐다! 이제 문제를 풀 수 있게 되었다. 
n! / ((n-m)!*m!)에서 끝자리 0의 갯수는 2*5쌍의 수를 세는 것이므로 n! 의 2*5 쌍의 수 - ((n-m)! 의 2*5의 쌍 수 + m! 의 2*5 쌍의 수)이다.

 

앞서 팩토리얼의 0의 수를 일일이 for문으로 풀었던 나로서는 이 문제를 푸는데 고심했어야 했지만 아마 지금의 풀이과정과 동일하게 접근하신 분이라면 동치인 문제로 보고 쉽게 풀어낼 수 있었으리라 생각한다. 

 

<조합 0의 개수 소스코드>

import java.util.*;

public class Main {
	public static void main(String[] args) {

		// nCm에서 0의 개수
		// n!/(n-m)!*m!
		// 끝자리 0의 갯수는 10이 얼마나 있느냐 = 2*5의 갯수
		// 25P12 / 12!
		// 25! / (13! * 12!)
		// 25 24 23 22 21 20 19 18 17 16 15 14 13 / 5: 4
		// 12 11 10 9 8 7 6 5 4 3 2 1 / 5 : 2
		// 5 10 15 20 25
		// 25 -> 5 10 15 20 25 -> 5 : 6
		// 5 10 -> 5:4 / 2 ~ 12 /
		// 5 10 15 20 25 30 35 40 45
		// 1 1 1 1 2 1 1 1 1
		// 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120
		// 125
		// 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3

		Scanner sc = new Scanner(System.in);

		long n = sc.nextInt();
		long m = sc.nextInt();
		long five = cntFive(n) - cntFive(m) - cntFive(n - m);
		long two = cntTwo(n) - cntTwo(m) - cntTwo(n - m);
		if (m == 0) {
			System.out.println(0);
		} else {
			System.out.println(Math.min(five, two));
		}

	}

	private static long cntFive(long n) {
		long cntFive = 0;
		for (long i = 5; i <= n; i *= 5) {
			cntFive += n / i;
		}
		return cntFive;
	}

	private static long cntTwo(long n) {
		long cntTwo = 0;
		for (long i = 2; i <= n; i *= 2) {
			cntTwo += n / i;
		}
		return cntTwo;
	}
}

 

참고 - <팩토리얼 0의 개수>

1. 무지성 for문 버전

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int cnt = 0;
		int temp = 0;
		int index = new Scanner(System.in).nextInt();
		for (int i = 5; i <= index ; i+=5) {
			temp = i;
			while(temp % 5 == 0 && temp != 0) {
				cnt++;
				temp /= 5;
			}
		}
		System.out.println(cnt);
	}
}

2. 수학적 접근 버전

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(cntTen(n));
        
		}
	private static int cntTen(int n) {
		int cntFive = 0;
        int cntTwo = 0;
        
		for (int i = 5; i <= n; i *= 5) {
			cntFive += n / i;
		}
        for (int i = 2; i <= n; i *= 2) {
            cntTwo += n / i;
        }
        int cnt = Math.min(cntFive, cntTwo);
        
		return cnt;
	}
}

오늘로써 단계별로 풀어보기의 정수론 및 조합론 부분을 끝냈다. 다음 진도 스택을 이미 다 풀었으므로 큐, 덱 부분을 도전할 예정이다.