구슬을 나누는 경우의 수

문제

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

조건

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

예시

balls	share	result
3	2	3
5	3	10

풀이

• 반복문을 돌 때마다 분모, 분자값을 한 번에 answer에 곱하고 나누려고 했으나 정수가 아닌 값 발생
• 두 개의 변수에 분자, 분모에 들어갈 모든 값을 다 곱해놓고 한번에 나누려고 했으나 범위 초과
• long 으로 타입을 바꿔봤으나 범위 초과
• 분자와 분자에 들어갈 값들을 배열에 저장하여 관리하고, 분모의 값으로 나눌 수 있으면 나눈 후 정리하려고 했으나 범위를 초과하는 값 잔존
• n개 중 x개를 고르는 경우의 수와 (n-x)개를 고르는 경우의 수는 차이가 없으므로 초기에 작은 값으로 변환하는 코드 추가

코드

class Solution {
    public int solution(int balls, int share) {
        int answer = 1;
        share = Math.min((balls-share), share);
        if(share == 0){
        	return 1;
        }
        
        int[] up = new int[share];
        int[] down = new int[share];
        
        for(int i = 0; i < share; i++){
            up[i] = (balls - i);
            down[i] = (share - i);
        }
        
        for(int i = 0; i < share; i++){
            for(int j = 0; j < share; j++){
                if(up[j] % down[i] == 0){
                    up[j] = up[j] / down[i];
                    down[i] = 1;
                    break;
                }
            }
        }
        
        for(int e : up){
            answer *= e;
        }
        for(int e : down){
            answer /= e;
        }
        
        return answer;
    }
}