[백준] 단계별로 풀어보기(단계:17,정수론 및 조합론,JAVA)2004번, 조합 0의 개수

문제 링크

2004번: 조합 0의 개수

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

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

---

문제 설명

---

접근 방법

이 문제는 0이 나오려면 10의 배수가 나와야 하는데 10 = 5*2로 표현이 가능합니다.

이항계수을 연산할 때 2의 배수가 많은지 5의 배수가 더 많은지 알 수 없습니다.

그래서 2의 배수와 5의 배수를 모두 구하여 더 많은 것을 기준으로 0의 개수라고 판단합니다.

반복문을 통해서 2의 배수와 5의 배수의 숫자를 찾아서 비교하는 방식으로 설계하였습니다.이항 계수의 기본 공식은 nCm = n!/m!(n-m)!입니다. 여기서 팩토리얼 간에 약분이 진행되기 때문에2의 배수의 개수를 구할 때n!의 2의 배수 - m!의 2의 배수 - (n-m)!의 2의 배수위와 같은 알고리즘이 나옵니다. 빼기를 하는 이유는 약분이 되면 그에 해당하는 2의 배수가 사라지기 때문입니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 2의 배수 개수를 구하는 함수 twodivisorCal, 5의 배수 개수를 구하는 함수 fivedivisorCal을 만들었습니다.
• 2의 배수와 5의 배수중 더 큰 것을 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 저장된 결과를 출력하였습니다.

• twodivisorCal과 fivedivisorCal은 동일하게 while문을 통하여 반복하여 2의 배수와 5의 배수의 개수를 구합니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //-----------입력 값 저장-------------
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	int N = Integer.parseInt(st.nextToken());
    	int K = Integer.parseInt(st.nextToken());
    	int temp = N-K;	//(n-m)!
    	int two = twodivisorCal(N) - twodivisorCal(K) - twodivisorCal(temp);
    	int five = fivedivisorCal(N) - fivedivisorCal(K) - fivedivisorCal(temp);
    	bw.write(Math.min(two, five) + "\n");	//2의 배수, 5의 배수 개수 중 더 큰 것 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
    //2의 배수 개수 구하는 함수
	public static int twodivisorCal(int num) {
		int result = 0;
		long temp = 2;
		while(true) {
			if(num/temp<1)
				break;
			result += num/temp;
			temp *= 2;
		}
		return result;
	}
    //5의 배수 개수 구하는 함수
	public static int fivedivisorCal(int num) {
		int result = 0;
		long temp = 5;
		while(true) {
			if(num/temp<1)
				break;
			result += num/temp;
			temp *= 5;
		}
		return result;
	}
}