[프로그래머스] 구슬을 나누는 경우의 수 Java

문제 설명

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

 

제한사항

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

 

입출력 예

 

코드

class Solution {
    public int Combi(int n, int r){
        if(n==r||r==0){
            return 1;
        }
        return Combi(n-1,r-1)+Combi(n-1,r);
    }
    
    public int solution(int balls, int share) {
        int answer = Combi(balls, share);
        return answer;
    }
}

문제에서 공식을 주길래 처음에는 공식 그대로 코드에 적용했는데 자꾸 오류 났음. 보니까 값이 너무 커져서 그렇다는 말이 많길래 원래 알고있던 공식으로 다시 코드 짰다. nCr = n-1Cr-1 + n-1Cr만 알고있으면 쉽게 풀릴 듯

 

문제 출처

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