[BOJ] 2004. 조합 0의 개수 - JAVA

🔗 문제

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

2004번: 조합 0의 개수

 

🧩 풀이 및 코드

문제 유형 : 수학, 정수론

 

풀이

문제는 nCr 의 0의 갯수를 구하는 것이다.

여기서 수학 공식 한 개를 알아야 한다.

우선 팩토리얼의 0의 갯수부터 구해보자.

예를 들어서 59! 의 0의 갯수를 구하려면 59! 을 소인 수 분해 했을 때 2 x 5 의 갯수가 몇 개인지 찾아야 한다. (10 이 몇 번 곱해졌는 지가 0의 갯수를 결정하므로)

59! = 59 x 58 x 57 x ... x 1 이다. 이 중 5의 배수는 59/5 = 11 개이다. 

11개를 적어보면 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55 이다. 이 수 이외의 숫자는 5를 소인수로 가지고 있지 않는다. 

이 중 25 = 5 x 5, 50 = 5 x 5 x 2, 는 5를 두번 가지고 있으므로 59! 의 5의 갯수는 13이다.

이를 계산하는 코드를 나타내면

static int get(int f, int k) {
		
    int res = 0;

    while(f>=k) {
        res += f/k;
        f/=k;
    }

    return res;
}

이다. 여기서 n! / (n-r)! r! 의 0의 갯수를 구하는 것이므로 n! 의 0 의 갯수 - (n-r)! 의 0의 갯수 - r! 의 0의 갯수를 구하면 된다.

2x5의 갯수를 구하는 것이므로 2와 5 중 적은 갯수가 정답이 된다.

 

느낀 점

어렵다 이걸 어떻게 생각해 내지

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_2004_조합0의개수 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_2004.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int R = sc.nextInt();
		
		int twoCnt = get(N, 2) - get(N-R, 2) - get(R, 2); 
		int fiveCnt = get(N, 5) - get(N-R, 5) - get(R, 5);
		
		
		System.out.println(Math.min(twoCnt, fiveCnt));
		sc.close();
	}
	
	static int get(int f, int k) {
		
		int res = 0;
		
		while(f>=k) {
			res += f/k;
			f/=k;
		}
		
		return res;
	}

}

 

---

Reference

https://mslim8803.tistory.com/11

백준(BOJ) 2004 : 조합 0의 개수 (JAVA)