Problem

---

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

Solution

---

내 수학은 초등학교에서 멈췄는데... 그게 중요한 건 아니고.

이 문제는 완전탐색이 아니라 정석적인 조합(combination) 문제다.
결국 구슬 n개 중에서 r개를 고르는 경우의 수를 구하는 수식으로 푸는데 (문제 사이트에 공식이 이미지로 나와 있다)

근데 이 문제를 팩토리얼 그대로 쓰면 오버플로우가 발생해서
중간중간 나눠서 곱셈으로 처리함으로써 오버플로우를 방지해야 한다고 한다.

🚀 예시
balls = 5, share = 3
👉 계산: 5 * 4 * 3 / (3 * 2 * 1) = 10

👉 “조합 구현 = 위에서 하나 곱하고, 아래에서 하나 나눈다를 반복”

i	계산
1	× n / 1
2	× (n-1) / 2
3	× (n-2) / 3

Code

---

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

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

        return (int) answer;
    }
}