구슬을 나누는 경우의 수
문제 #
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
- 제한사항
- 1 ≤
balls≤ 30 - 1 ≤
share≤ 30 - 구슬을 고르는 순서는 고려하지 않습니다.
share≤balls
- 1 ≤
- 입출력 예
balls share result 3 2 3 5 3 10
나의 풀이 #
class Solution {
public long solution(int balls, int share) {
return fact(balls)/fact(balls-share)/fact(share);
}
public static long fact(int num) {
if (num <= 1)
return num;
else
return fact(num-1)*num;
}
}
- 오버플로우발생
class Solution {
public long solution(int balls, int share) {
long numer = 1;
long denom = 1;
// n!/(n-m)!을 약분하여 (n-m+1)*...*(n-1)n을 분자로
for (int i = balls; i>=balls-share+1; i--) {
numer *= i;
}
// 분모 m!
for (int j = 1; j<=share; j++) {
denom *= j;
}
return numer / denom;
}
}
- 계산 결과를 최소한으로 하기위해 n!과 (n-m)!를 약분하였으나 (30,15)의 테스트케이스에서 오버플로 발생
다른 사람의 풀이 #
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;
}
}
- 반복문으로 표현하면
class Solution {
public long solution(int balls, int share) {
share = Math.min(balls - share, share);
if (share == 0)
return 1;
long result = 1;
for (int i = 0; i < share; i++) {
result *= balls - i; //n!/(n-m)!을 약분한 값
result /= i + 1; //m!
}
return result;
}
}
관련개념 학습 #
- [[]]