[코딩테스트 입문] 구슬을 나누는 경우의 수 (nCr) ★★★

🔸 문제 설명

서로 다른 구슬 balls개 중에서
share개의 구슬을 순서 없이 고르는 경우의 수를 구하는 문제입니다.

이건 수학에서 조합 (Combination)이라 부릅니다.
공식은 이렇게 생겼어요:

nCr = n! / (r! * (n - r)!)

 

🔸 입출력 예

balls	share	결과
3	2	3
5	3	10

 

❓ 내가 처음에 했던 방식 (팩토리얼 3번 계산)

a = balls!
b = (balls - share)!
c = share!
answer = a / (b * c)

근데 이 방식은 문제가 있음

 

❗ 실수했던 포인트

❌ 팩토리얼 계산이 너무 커짐 (오버플로우)

• 30! 같은 건 숫자가 long 타입보다 커짐
• 그래서 일부 테스트 케이스에서 틀린 결과 나옴
• 해결책 → BigInteger나 수학 공식을 활용해야 해!

 

✅ 가장 쉬운 방법 (곱하면서 바로 나누는 방식!)

class Solution {
    public int solution(int balls, int share) {
        long answer = 1;

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

        return (int) answer;
    }
}

 

💡 어떻게 동작하는 걸?

우리가 구하려는 건:

nCr = (n × (n-1) × (n-2) ... (n-r+1)) / (1 × 2 × 3 ... r)

이걸 반복문 하나로 계산하면 된다!
곱하고 → 바로 나누고!

 

✨ 예시: 5C3 계산 과정

5C3 = (5×4×3) / (1×2×3)

반복문에서:
answer = 1
→ 1 * 5 / 1 = 5
→ 5 * 4 / 2 = 10
→ 10 * 3 / 3 = 10

 

결과: ✅ 10

 

💬 느낀 점

처음엔 팩토리얼로 풀었더니 값이 너무 커져서 터졌었다 😥
하지만 수학 공식의 성질을 잘 이용하면
반복문 하나로 정확하고 빠르게 조합을 계산할 수 있었다!
곱하면서 동시에 나누는 방식이 이렇게 간단한 줄 몰랐다! 하지만 어렵다,,,