[코테 풀이] 구슬을 나누는 경우의 수

Q) 구슬을 나누는 경우의 수

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

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120840

class Solution {
    public int solution(int balls, int share) {
        int answer = 0;
        int[][] matrix = new int[balls+1][balls+1];
        for(int i = 0; i < balls+1; i++){
            matrix[i][i] = 1;
            matrix[i][1] = i;
            matrix[i][0] = 1;
        }
        
        for(int i = 2; i <= balls; i++){
            for(int j = 1; j < i; j++){
                matrix[i][j] = matrix[i-1][j] + matrix[i-1][j-1];
            }
        }
        
        answer = matrix[balls][share];
        return answer;
      
    }
}

인프런 강의를 참고했다.

조합의 점화식과 2차원 배열을 활용한 문제!
수학적으로만 풀려고 해서 런타임 에러가 떠버린..

내가 풀려고 했던 방식:

1) 5C3 = 4C3 + 4C2로 이루어질 수 있기 때문에 nCr = (n-1)C(r) + (n-1)C(r-1) 이라는 점화식이 나온다.

2) i개 중에 i를 고르는 경우의 수는 1, i개 중에 1개를 고르는 건 i개, i개 중 0개를 고르는 건 1이기 때문에 이차원 배열에 먼저 값을 삽입한다.

3) 그 뒤 가장 작은 값(i=2), 즉 트리 구조를 그렸을 때 leaf에 있는 경우부터 값을 채워넣는다.