[알고리즘문제풀기] 구슬을 나누는 경우의 수

문제

내가 작성한 오답

class Solution {
    public int solution(int balls, int share) {
        int answer = 1;
        for(int i = 1; i <= balls; i++){
            answer *= i;
        }
        for(int i = 1; i<= share; i++){
            answer /= i; 
        }
        for(int i = 1; i <= (balls-share); i++){
            answer /= i;
        }
            return answer;
    }
}

class Solution {
    public int solution(int balls, int share) {
        int answer = 1;
        
        for(int i = share+1; i <= balls; i++){
            answer *= i;
            answer /= i-share;
        }
        return answer;
    }
}

내가 작성한 정답

class Solution {
    public int solution(int balls, int share) {
        long answer = 1;

        for(int i = share+1; i <= balls; i++){
            answer *= i;
            answer /= i-share;
        }
        return (int)answer;
    }
}

다른 사람들의 정답

class Solution {
    public long solution(int balls, int share) {
		    // C(n, r) = C(n, n-r) 이므로, 작은 값으로 변환하여 계산량을 줄임
        share = Math.min(balls - share, share);

				// C(n, 0) = 1 이므로, 재귀 종료 조건
        if (share == 0)
            return 1;

				// 	C(n, r) = C(n-1, r-1) * (n / r)
        long result = solution(balls - 1, share - 1);
        result *= balls;
        result /= share;

        return result;
    }
}