BigInteger 없이 이 문제를 풀 수 있다면

문제 설명

문제 링크

프로그래머스

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

 

제한 사항

1. 1 <= balls <= 30
2. 1 <= share <= 30
3. 구슬을 고르는 순서는 고려하지 않습니다.
4. share <= balls

 

접근

이 문제가 재미있었던 이유는 서로 다른 n개 중 m개를 고르는 경우의 수 공식을 문제에서 공개했다. 재귀함수를 이용해 Factorial을 구현하면 풀 수 있는 문제라고 생각했으나, TC (30, 15)에서 int, long 타입으로 계산을 시도하는 경우 Overflow가 발생한다. 따라서 다른 방법이 필요했음.

두 번째로 고민한 방법은 Factorial 계산 전에 미리 약분을 해주는 건데, 이 케이스 역시 Overflow가 발생했다.

마지막 방법은 분자와 분모를 따로 구해 나누기를 해주는 것이 아니라, 먼저 나누고 곱하는 방식이었다. 이 경우 발생할 수 있는 문제는 9 / 3 경우와 같이 무한 소수가 나오는 경우 손실이 발생한다는 점. 케이스를 몇 개 더 그려보면서 시도했는데,

# CASE 1: 14개 중 6개를 고르는 경우
분자: 14 x 13 x 12 x 11 x 10 x 09
분모: 06 x 05 x 04 x 03 x 02 x 01

# CASE 2: 30개 중 15개를 고르는 경우
분자: 30 x 29 x 28 x 27 x 26 x 25 x 24 x 23 x 22 x 21 x 20 x 19 x 18 x 17 x 16
분모: 15 x 14 x 13 x 12 x 11 x 10 x 09 x 08 x 07 x 06 x 05 x 04 x 03 x 02 x 01

 

이런 식으로 분자와 분모의 개수가 같아진다.

분자의 범위: m + 1 <= numer <= n
분모의 범위: 1 <= denom <= m

 

그러면 CASE 1의 경우 `14/6 * 13/5 *, ..., * 9/1` 이런 식으로 계산할 수 있다.
문제는 여기서도 소수점 손실 문제가 발생할 수 있는데, 순서를 바꾸면 해결이 가능하다.

CASE 1의 경우 `14 / 1 * 13 / 2 * 12 / 3 ...`과 같이 진행되는데, 분자의 소인수가 분모의 소인수를 전부 포함하고 있을 것이라는 생각에서 시도했다.

그런데 아직 분자의 소인수가 분모의 소인수를 포함하지 않는 경우나(반례), 분자의 소인수가 분모의 소인수를 모두 포함하고 있을 거라는 예측을 증명 못함.
그래서 어떤 케이스든 나누어 떨어진다고 하기 애매하고, 그냥 추측이지만 시도해 보았다.

추측: 분자의 소인수가 분모의 소인수를 모두 포함하고 있을 것이다.

 

코드

public class PRGRMS_120840 {

    public int solution(int balls, int share) {
        long answer = 1;
        for (int i = 1; i < share + 1; i++) {
            answer *= (balls - i + 1);
            answer /= i;
        }

        return (int) answer;
    }
}

 

 

---

이후에 추측이 맞는지 좀 더 찾아보았다.
n개 중 m개를 고르는 경우는 n과 m이 모두 자연수이고, `n >= m`이다. 코드에서 for문으로 계산되는 answer 값은 n개 중 i개를 고르는 경우에 해당한다.
반드시 모든 소인수가 포함되기 때문에, 소수점이 발생하지 않고 답은 자연수가 된다.

이 문제는 BigInteger를 이용해서 풀면 쉽게 풀 수 있으나, 이렇게 접근해 보는 것도 재미있었다.