[Programmers] Lv.0 | 구슬을 나누는 경우의 수 | Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120840

 

풀이

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

 

---

 

💡 조합 계산 완전 정복 — 팩토리얼 없이 안전하게 구하기

코딩테스트에서 정말 자주 나오는 대표적인 수학 개념 중 하나가 조합(Combination)

• 예: “구슬 N개 중 R개를 고를 수 있는 경우의 수”를 구하라는 문제

처음엔 공식만 외워서 구현하려다 팩토리얼로 인한 오버플로우나 공식이 왜 그렇게 되는지 이해 안 되는 상황이 자주 발생함
그래서 이번 글에서는

• ✅ 조합이 뭔지
• ✅ 공식이 어떻게 만들어지는지
• ✅ 팩토리얼 대신 단계별로 계산하는 이유
• ✅ long 타입을 쓰는 이유
  까지 전부 정리

 

🪄 1. 조합이란?

조합(Combination)은 순서를 고려하지 않고 n개 중 r개를 고르는 경우의 수를 말함

예: 구슬 3개 중 2개를 고른다고 가정

{A, B}, {A, C}, {B, C}

👉 총 3가지 방법이 존재함

 

수학적 표현:

• ( n ): 전체 개수
• ( r ): 고르는 개수

 

🧮 2. 조합의 기본 공식

조합의 기본 공식은 아래와 같음

 

예: 5개 중 3개 고르기 → ( 5C3 )

즉, 10가지 조합이 생김

 

🧠 3. 공식이 그렇게 나오는 이유

처음에 5개 중 3개를 순서를 고려해서 뽑는 경우를 생각해보면:

• 1번째: 5개 중 선택
• 2번째: 4개 중 선택
• 3번째: 3개 중 선택

👉 ( 5 × 4 × 3 = 60 )가지 경우

 

하지만 조합에서는 순서를 신경 쓰지 않기 때문에
예: A-B-C, B-A-C, C-B-A … 모두 같은 경우로 취급됨

3개를 뽑을 때 순서가 바뀌는 경우의 수는 ( 3! = 6 )가지

 

그래서

이 되는 거고, 공식도

의 형태로 단순화됨
👉 (n - r)! 부분이 약분돼서 사라지는 것

 

🚫 4. 팩토리얼을 직접 쓰면 안 되는 이유

처음에는 많이들 이렇게 구현함:

return factorial(n) / (factorial(n - r) * factorial(r));

 

하지만 이 방식에는 문제가 있음

1. 팩토리얼 값이 너무 빨리 커짐
   • 20!만 해도 2,432,902,008,176,640,000
   • int나 long으로도 감당 안 되는 값이 금방 나옴
2. 불필요한 연산이 많음 (계산했다가 다시 나눔)
3. 성능 저하 + 오버플로우 위험

그래서 팩토리얼 자체를 계산하지 않고, 공식을 단계별 곱셈·나눗셈으로 바꿔서 계산함

 

🪄 5. 팩토리얼을 쓰지 않고 단계별로 계산하기

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

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

        return (int) result;
    }
}

 

🧭 6. 코드 설명 

변수	의미	수학 기호
balls	전체 구슬 개수	n
share	뽑는 구슬 개수	r
i	현재 몇 번째 뽑는 중인지 (1부터 r까지)	-
result	누적 계산 값	nCr

 

(balls - i + 1)은 분자에서 점점 줄어드는 선택지를 의미
/ i는 분모에서 중복되는 순서를 제거하는 부분

 

예: balls=5, share=3일 때

i	분자 (balls - i + 1)	분모 (i)	result 계산
1	5	1	1 × 5 ÷ 1 = 5
2	4	2	5 × 4 ÷ 2 = 10
3	3	3	10 × 3 ÷ 3 = 10

👉 최종 결과 = 10 ✅

 

🧱 7. long 타입을 사용하는 이유

• int는 약 21억까지만 저장 가능 (2,147,483,647)
• 하지만 팩토리얼이나 조합 중간 계산값은 훨씬 커질 수 있음
• balls의 최대값이 30이라도 중간 계산값이 int 범위를 넘을 수 있음

따라서 중간 계산을 long으로 처리하고 마지막에 int로 변환해도 안전함

 

📝 정리 요약

항목	잘못된 방식 ❌	올바른 방식 ✅
구현 방법	팩토리얼로 직접 계산	단계별 곱셈/나눗셈
오버플로우 위험	높음	낮음
성능	불필요한 계산 많음	계산 간결
자료형	int	long 사용 후 int 변환

공식을 그대로 단계별로 풀어 쓰면 팩토리얼 없이도 조합을 정확하게 구할 수 있음

 

🏁 마무리

• 조합 공식은 <순서를 제거한 경우의 수>라는 개념에서 출발함
• 팩토리얼을 직접 쓰면 중간 값이 너무 커지므로 피하는 것이 좋음
• 곱셈과 나눗셈을 루프로 나누어 처리하면 안전하고 깔끔하게 계산 가능
• 자료형은 반드시 long을 사용하기