[백준] 2004번 : 조합 0의 개수 - JAVA [자바]

 
www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

---

• 문제

 

 

 

 

이전의 팩토리얼 0의 개수를 정확히 이해하고 풀었다면 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

먼저 이 문제를 풀기 전에 아래 글에서 다루고 있는 0의 개수를 세는 방식을 이해하기 위해 보는 것을 추천한다.

st-lab.tistory.com/165

[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]

 

 

이전 문제를 풀어봤다면 알겠지만, 한 팩토리얼 값에 2와 5의 승수가 겹치는 수를 구하는 것이 관건이다.

문제에서 나와있길 nCm 을 구하는 문제이기 때문에 결국 이항 계수의 공식을 생각하면 된다. 이항 계수의 공식은 팩토리얼 값으로 공식이 이루어져 있기 때문에 이를 이용하면 매우 쉽게 풀 수 있다는 것이다.

 

일단 이항 계수를 구하는 공식은 다음과 같다.

 

 

여기서 0의 개수는 2와 5의 겹치는 승수의 값과 같다. 즉, n!, (n-m)!, m! 의 2와 5의 승수를 구한다.

 

좀 더 쉽게 설명하자면 이렇다. 위 nCm에서 2와 5의 승수를 뽑는다고 할 때 다음과 같이 표현 할 수 있다.

 

 

여기서 2의 승수(a₁ - b₁, c₁) 와 5의 승수(a₂ - b₂ - c₂) 가 구해졌으면 이제 겹치는(짝지을 수 있는) 개수를 구하면 되므로, 2와 5의 승수 중 최솟값을 출력하면 된다.

 

이를 알고리즘으로 짜자면 이렇다.

 

void main()	{

	long N = inputLong();
	long M = inputLong();
	
	// 각각의 승수를 구해준다.
	long count5 = five_power_n(N) - five_power_n(N - M) - five_power_n(M);
	long count2 = two_power_n(N) - two_power_n(N - M) - two_power_n(M);
        
	print(min(count5, count2));
		
}
	
// 5의 승수를 구하는 함수 
long five_power_n(long num) {
	int count = 0;
		
	while(num >= 5) {
		count += num/5;
		num /= 5;
	}
	return count;
}
	
// 2의 승수를 구하는 함수
long two_power_n(long num) {
	int count = 0;
		
	while(num >= 2) {
		count += num/2;
		num /= 2;
	}
	return count;
}

 

 

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

입력의 방식을 달리하여 성능 비교를 해보고자 한다. 알고리즘은 위의 방식을 그대로 쓸 것이다.

 

1 . Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		long N = in.nextLong();
		long M = in.nextLong();
		
		// 각각의 승수를 구해준다.
		long count5 = five_power_n(N) - five_power_n(N - M) - five_power_n(M);
		long count2 = two_power_n(N) - two_power_n(N - M) - two_power_n(M);
        
		System.out.println(Math.min(count5, count2));
		
	}
	
	// 5의 승수를 구하는 함수 
	static long five_power_n(long num) {
		int count = 0;
		
		while(num >= 5) {
			count += (num / 5);
			num /= 5;
		}
		return count;
	}
	
	// 2의 승수를 구하는 함수
	static long two_power_n(long num) {
		int count = 0;
		
		while(num >= 2) {
			count += (num / 2);
			num /= 2;
		}
		return count;
	}

}

 

 

문제만 정확히 이해한다면 어렵지 않게 풀 수 있다.

 

참고로 이번에는 입력값이 20억이 넘기 때문에 안전하게 long 타입으로 받자.

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		long N = Long.parseLong(st.nextToken());
		long M = Long.parseLong(st.nextToken());

		// 각각의 승수를 구해준다.
		long count5 = five_power_n(N) - five_power_n(N - M) - five_power_n(M);
		long count2 = two_power_n(N) - two_power_n(N - M) - two_power_n(M);
		System.out.println(Math.min(count5, count2));

	}

	// 5의 승수를 구하는 함수
	static long five_power_n(long num) {
		int count = 0;

		while (num >= 5) {
			count += (num / 5);
			num /= 5;
		}
		return count;
	}

	// 2의 승수를 구하는 함수
	static long two_power_n(long num) {
		int count = 0;

		while (num >= 2) {
			count += (num / 2);
			num /= 2;
		}
		return count;
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 23699382  -  방법 2 : BufferedReader

채점 번호 : 23699379  -  방법 1 : Scanner

 

 

언제나 그렇듯 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 문제가 생각보다 정답률이 낮았다. 이전 팩토리얼 0의 개수 구하는 문제는 정답률이 높은 걸 보아 이 문제에 대해 풀이 방법은 알아도 정확한 개념 이해로 알게 된 것이 아니여서 그러지 않을까 싶다. 만약 개념만 정확하게 이해했다면 정말 쉽게 풀 수 있는 문제라..

위 알고리즘대로라면 int형으로 받아도 상관 없기 때문에 아마 범위 문제라면 필자와 다른 알고리즘을 사용하면서 해당 알고리즘에 입력값을 더하거나 곱하는 과정이 포함되어있을 수 있다.

 

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.