[Baekjoon] 2407번 조합(Java)

package Q2407;

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		BigInteger n = new BigInteger(scan.next());
		BigInteger r = new BigInteger(scan.next());		
		
		// divide: 나누기, multiply: 곱하기, subtract: 빼기
		System.out.println(fac(n).divide(fac(r).multiply(fac(n.subtract(r)))));
	}
	
	public static BigInteger fac(BigInteger n) {
		if(n.compareTo(new BigInteger("0")) == 1) {	// a.compareTo(b) -> a=b : 0, a>b : 1, a<b : -1
			return n.multiply(fac(n.subtract(new BigInteger("1"))));
		}else {
			return new BigInteger("1");
		}
	}
}

조합 공식을 사용해서 풀었다.

 

조합의 경우의 수를 구하는 공식
nCr = n! / r!(n - r)!

 

기존에 팩토리얼을 구현했었던 코드가 있어서 사용을 했는데 100을 입력했을 때 계속 0이 나와서 멘탈이 나갔었다.

알고 보니 자바에서 큰 수를 표현할 때 int나 long으로 표현할 수 있는 수의 범위를 넘어가면 BigInteger 클래스를 사용해야 한다고 한다. BigInteger로 바꾸어서 풀었더니 금방 풀린 문제였다.