구슬을 나누는 경우의 수 (자바, Java)

조합, 이항계수 문제다. 3C2 = 3, 5C2 = 10같은 경우인데,

백준에서 풀때 느꼈지만, 팩토리얼은 조금만 숫자가 커져도 금방 자릿수가 기하급수적으로 증가한다.

따라서 double로도 커버가 안되고, BigInteger를 써주는 편이 좋다.

힌트에서 조합 공식을 소개했으나, 숫자가 빠르게 커지는 점이나, 연산량이 많아지는 점을 고려하여

나는 nPm/m! 으로 풀었다.

 

import java.math.BigInteger;

class Solution {
    public int solution(int balls, int share) {
        int answer = 0;
        BigInteger bi = permutation(balls, share).divide(permutation(share, share));

        answer = bi.intValue();        		
        return answer;
    }
    
    public BigInteger permutation(int n, int r) {
        BigInteger p = new BigInteger("1");
        for (int i=n; i>=n-r+1; i--) {
            p = p.multiply(BigInteger.valueOf(i));
        }
        return p;
    }
}