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

문제

내가 작성한 오답

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

내가 작성한 정답

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

다른 사람들의 정답

public long solution(int balls, int share) {
    share = Math.min(balls - share, share);  // ① k 최적화 (nCk = nC(n-k))
    
    if (share == 0) return 1;                // ② 기본 케이스
    
    long result = solution(balls - 1, share - 1);  // ③ 재귀 호출
    result *= balls;
    result /= share;
    return result;
}