조합(combination) 구하기

---

 

 

 

n가지중 r개를 선택하는 방법, 즉 조합의 공식이다.

n과 r을 입력받아 조합의 수를 구하는 코드를 짜보았다.

int, long으로는 커버할 수 없는 수까지 금방 올라가기에 BigInteger 클래스를 사용했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class ex {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();

		int N = Integer.parseInt(input.split(" ")[0]);
		int R = Integer.parseInt(input.split(" ")[1]);
		int N_original = N;

		br.close();

		BigInteger solution = BigInteger.ONE;

		int dif = R > N/2 ? N-R : R;

		while(dif != 0) {

			solution = solution.multiply(BigInteger.valueOf(N));
			N -= 1;
			dif -= 1;

		}

		solution = R > N_original/2 ? solution.divide(factorial(N_original-R)) :                 solution.divide(factorial(R));

		System.out.println(solution);

	}

	public static BigInteger factorial(int n) {

		if (n <= 1)

			return BigInteger.ONE;

		BigInteger k = BigInteger.ONE;

		for (int i = 2; i <= n; i++) {

			k = k.multiply(BigInteger.valueOf(i));

		}

		return k;

	}

}

 

 

 

---