[프로그래머스] 구슬을 나누는 경우의 수 - Java

문제

링크

---

코드

class Solution {
    public int solution(int balls, int share) {
        return combination(balls, share);
    }

    public static int combination(int balls, int share) {
        if (balls == share || share == 0) return 1;
        return combination((balls - 1), (share - 1)) + combination(balls - 1, share);
    }
}

---

리뷰

코드는 간단한 것에 비해 생각보다 어려웠던 문제였다.

해당 식을 적용하여 재귀함수를 통해 구현하였다.

예를들어, 문제처럼 3개의 구슬(1, 2, 3) 중 2개를 뽑는다고 가정하면
3C2 = 2C2 + 2C1 이다.
1, 2, 3 중 1을 뽑지 않는 경우 2, 3을 모두 뽑아야 하므로 => 2C2
1, 2, 3 중 1을 뽑은 경우 2, 3 중 1개를 뽑아야 하므로 => 2C1

이렇게 수식을 이해하고나면 재귀함수를 구현하면된다.

공의 개수와 뽑을 개수가 같거나 0개를 고르는 경우는 경우의 수가 1이므로 1을 반환하고 그 외에는 위의 식을 이용해 경우의 수를 반환하도록 한다.