[JAVA, Programmers] 구슬을 나누는 경우의 수(자바)

1. 문제 설명

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

 

2. 제한사항

1 ≤ balls ≤ 30

1 ≤ share ≤ 30

구슬을 고르는 순서는 고려하지 않습니다.

share ≤ balls

 

3. 입출력 예

balls	share	result
3	2	3
5	3	10

 

4. 입출력 예 설명

- 입출력 예 #1

서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.  

- 입출력 예 #2

서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.

 

Hint

서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다.  

 

5. 풀이(오류)

class Solution {
    public int solution(int balls, int share) {
        long a =1; long b =1;
		while(balls-share>0) {
			a *= balls; 
			b *= (balls-share);
			balls--;
		}
        return (int) (a/b);
    }
}

Hint 공식을 좀더 간결하게 해석했다.

ex) n = 5, m = 3 일 때

 

분모 : 5! : 5 * 4 * 3* 2 * 1

분자 : (5-3)!*3! : (2 * 1 ) * 3 * 2 * 1

3!이 분자, 분모 각각 소거되면 

5*4 / 2*1이 된다. 

분모 : n을 m-n회 1씩 뺀 수의 곱 : 5를 2회 1씩 뺀 수의 곱

분자 : n-m을 1씩 뺀 수의 곱 : 2를 1씩 뺀 수의 곱

 

쉽게 풀릴 줄 알았다. 그런데 

실패가 나왔다.. 주어진 값에 따라 long보다 커지는 경우가 생기기 때문이다. 해결하기 위해 

처음으로 BigInteger를 사용해 보았다..

 

6. 재풀이

import java.math.*;
class Solution {
    public int solution(int balls, int share) {
        BigInteger a = new BigInteger("1");
        BigInteger b = new BigInteger("1");
        while(balls-share>0) {
            BigInteger B = BigInteger.valueOf(balls);
            BigInteger S = BigInteger.valueOf(share);
            a= a.multiply(B); 
            b = b.multiply(B.subtract(S));
            balls--;
        }
        a = (a.divide(b));
        int answer = a.intValue();

        return answer;
    }
}

int 와 long 이상의 수를 문자형태로 받는다. 

산술연산에 메서드를 사용해야한다.

 

이건 아닌 것 같아서 다른 분의 엄청난 풀이를 보며 다시 공부하였다....

 

7. 다른 분의 풀이

class Solution {
    public long solution(int balls, int share) {
        share = Math.min(balls - share, share);

        if (share == 0)
            return 1;

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

        return result;
    }


}

[해석에 도움을 주신 분의 출처]

https://copro505.tistory.com/entry/%EA%B5%AC%EC%8A%AC%EC%9D%84-%EB%82%98%EB%88%84%EB%8A%94-%EA%B2%BD%EC%9A%B0%EC%9D%98-%EC%88%98

구슬을 나누는 경우의 수→순수(?) 조합 계산★★