[Programmers] #120840 - 구슬을 나누는 경우의 수 [Java][C++][Python]

문제 링크

---

1. 아이디어

서로 다른 구슬 balls개 중 share개를 순서 상관없이 고르는 경우의 수, 즉 이항계수 $\binom{n}{r}$($n$ = balls, $r$ = share)를 구하는 문제다. 정의대로 각 팩토리얼을 따로 계산해 나누면 값이 금세 커져 오버플로 위험이 있으므로, $\binom{n}{r} = \prod_{i=1}^{r} \dfrac{n-i+1}{i}$ 형태로 매 단계 새 분자 하나를 곱한 뒤 그에 대응하는 분모로 나누는 방식으로 한 항씩 누적한다. $i$번째 단계까지의 부분 결과는 항상 $\binom{n}{i}$ 형태의 정수이므로, 매 단계에서 나눗셈이 정확히 나누어떨어져 중간 계산을 정수로만 유지할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(R)$	$O(1)$

($R$ = share의 값)

---

3. 코드

풀이 [Java][C++][Python]

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

        return (int) ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

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

    return (int)ans;
}

from math import comb


def solution(balls, share):
    return comb(balls, share)

Python은 표준 라이브러리의 math.comb가 이항계수 계산을 직접 제공해 위 누적 곱셈을 직접 구현할 필요가 없다.

---