[Programmers] [Java] [120840] 구슬을 나누는 경우의 수

문제

• 번호 : 120840
• 제목 : 구슬을 나누는 경우의 수
• 난이도 : Level 0
• 서로 다른 balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수
• 문제 : 링크

---

필요 알고리즘

• 재귀 함수에 대한 이해가 필요하다.
• 조합수에 대한 간단한 이해가 필요하다. (고등학교 수학)
  • 조합수는 n개의 요소에서 r개의 요소를 선택하는 경우의 수이다.
  • 이 글에서는 n개의 요소에서 r개의 요소를 선택하는 조합수를 comb(n,r)이라 할 것이다.
  • 조합수의 성질
    • comb(n,r) == comb(n, n-r) : n개의 요소에서 r개를 택하는 것은, 나머지 n-r개를 결정하는 것과 같다.
    • comb(n,1) == comb(n,n-1) == n : n개의 요소에서 1개를 택하는 경우의 수는 n가지이다.
    • comb(n,0) == comb(n,n) == 1 : n개의 요소에서 0개를 택하는 경우의 수는 1가지이다.
    • comb(n,r) == comb(n-1, r-1) + comb(n-1, r)
      • n개의 요소에서 r개를 택하는 것은 어떤 특정 요소를 반드시 포함하는 경우와, 반드시 포함하지 않는 경우의 수의 합과 같다.
• 메모이제이션을 이용해, 연산 결과를 캐싱해두면 연산 속도를 크게 향상 시킬 수 있다. 한번 계산한 결과는 다시 계산할 필요 없이, 캐싱해둔 결과를 재사용한다.

---

풀이1 : comb(n,r) == comb(n-1, r-1) + comb(n-1, r)

public class Solution1 {

    private int[][] combinations;

    public int solution(int balls, int share) {
        combinations = new int[balls+1][balls+1];
        return combination(balls, share);
    }

    private int combination(int n, int r) {
        if (combinations[n][r] > 0) {
            return combinations[n][r];
        }
        if (r == 0 || r == n) {
            return combinations[n][0] = combinations[n][n] = 1;
        }
        if (r == 1 || r == n-1) {
            return combinations[n][1] = combinations[n][n-1] = n;
        }
        return combinations[n][r] = combinations[n][n-r] = combination(n-1, r-1) + combination(n-1, r);
    }

}

• 조합수들을 이차원 배열 combinations에 캐싱한다.
• 이 풀이에서는 comb(n,r) == comb(n-1, r-1) + comb(n-1,r) 임을 활용했다.
• 캐싱한 결과가 있으면 바로 꺼내 쓰고, 캐싱한 결과가 없으면 재귀적으로 계산하여 결과를 반환한다.
• 합을 통해 조합수를 구하기도 하고, 조합수의 범위가 int를 벗어나지 않으므로 int로도 충분하다.
• 이 방식은 조합수를 구하는 가장 일반적인 방법이므로 기억해두면 좋다.

---

풀이2 : comb(n,r) == comb(n-1, r-1) * n / r

public class Solution2 {

    private static long[][] combinations;

    public long solution(int balls, int share) {
        combinations = new long[balls+1][balls+1];
        return combination(balls, share);
    }

    private long combination(int n, int r) {
        if (combinations[n][r] > 0) {
            return combinations[n][r];
        }
        if (r == 0 || r == n) {
            return combinations[n][0] = combinations[n][n] = 1;
        }
        if (r == 1 || r == n-1) {
            return combinations[n][1] = combinations[n][n-1] = n;
        }
        long result = combination(n-1, r-1);
        result *= n;
        result /= r;
        return combinations[n][r] = combinations[n][n-r] = result;
    }

}

• 풀이1과 마찬가지로 메모이제이션을 적극 활용했다.
• 다만 여기서 곱 연산과, 나눗셈을 사용하므로 int 범위를 벗어날 가능성이 있다보니, long을 사용했다.

---

풀이3  : 팩토리얼 값 이용

import java.math.BigInteger;

public class Solution3 {

    private BigInteger[] factorials;

    public int solution(int balls, int share) {
        factorials = new BigInteger[balls+1];
        return combination(balls, share);
    }

    private int combination(int n, int r) {
        return factorial(n)
                .divide(factorial(n-r))
                .divide(factorial(r))
                .intValue();
    }

    private BigInteger factorial(int n) {
        if (factorials[n] != null) {
            return factorials[n];
        }
        if (n == 0 || n == 1) {
            return factorials[n] = BigInteger.ONE;
        }
        return factorials[n] = BigInteger.valueOf(n).multiply(factorial(n-1));
    }
}

• 조합수를 구하는 기본 공식 comb(n,r) == n! / (n-r)! * r! 을 사용하였다. (이는 문제에서 힌트로 제공된다.)
• 이 경우 팩토리얼 값의 long조차도 벗어나므로 BigInteger를 사용해야한다.
• 세 개의 팩토리얼 값을 계산해야하는데, 팩토리얼 값을 다시 계산하는 것보다 캐싱한 값을 쓰는게 더 시간적으로 이익이므로 캐싱을 했다.

---