✍스펙업/코딩테스트

구슬을 나누는 경우의 수 (Combination 재귀 함수 사용)

우동한그릇 2023. 7. 12. 17:58
반응형

 

class Solution {
    public int solution(int balls, int share) {
        return combination(balls, share);
    }
    
    public int combination(int n, int r) {
        if (r == 0 || n == r) {
            return 1;
        } else {
            return combination(n - 1, r - 1) + combination(n - 1, r);
        }
    }
}

 


# 구해야하는 조합.

combination(5, 3) = ①combination(4, 2) + ②combination(4, 3)

 

return combination(n - 1, r - 1) + combination(n - 1, r);

 

 기본적으로 조합은 선택하는 경우와 선택하지 않는 경우로 나눌 수 있다.

따라서 combination(n-1, r-1)은 n번째 원소를 선택한 경우의 수를 계산하고, 

combination(n-1, r)은 n번째 원소를 선택하지 않은 경우의 수를 계산한다.

 

이 두 개의 경우를 더하면 전체적인 조합의 개수를 구할 수 있다.

  
# 첫 번째로 combination(4, 2)를 계산


combination(4, 2) = combination(3, 1) + combination(3, 2)

여기서 combination(3, 1)은 3개의 원소 중에서 1개의 원소를 선택하는 경우의 수를 계산하고,

 combination(3, 2)는 3개의 원소 중에서 2개의 원소를 선택하는 경우의 수를 계산합니다.

combination(3, 1) = combination(2, 0) + combination(2, 1)
combination(2, 0)은 2개의 원소 중에서 0개의 원소를 선택하는 경우의 수로서 1을 반환합니다. 

combination(2, 1)은 2개의 원소 중에서 1개의 원소를 선택하는 경우의 수로서 2를 반환합니다.
따라서 combination(3, 1) = 1 + 2 = 3입니다.

 

combination(3, 2) = combination(2, 1) + combination(2, 2)
combination(2, 1)은 2개의 원소 중에서 1개의 원소를 선택하는 경우의 수로서 2를 반환합니다. 

combination(2, 2)는 2개의 원소 중에서 2개의 원소를 선택하는 경우의 수로서 1을 반환합니다.
따라서 combination(3, 2) = 2 + 1 = 3입니다.

그러면 combination(4, 2)를 계산합니다.
combination(4, 2) = combination(3, 1) + combination(3, 2)


이전에 계산한 결과를 대입하면 다음과 같습니다.

combination(4, 2) = 3 + 3 = 6

 

# 두 번째로 combination(4, 3)를 계산

combination(4, 3) = combination(3, 2) + combination(3, 3)
첫 번째로 combination(3, 2)를 계산해보겠습니다.

combination(3, 2) = combination(2, 1) + combination(2, 2)
여기서 combination(2, 1)은 2개의 원소 중에서 1개의 원소를 선택하는 경우의 수를 계산하고,

 combination(2, 2)는 2개의 원소 중에서 2개의 원소를 선택하는 경우의 수를 계산합니다.

combination(2, 1) = combination(1, 0) + combination(1, 1)
combination(1, 0)은 1개의 원소 중에서 0개의 원소를 선택하는 경우의 수로서 1을 반환합니다. 

combination(1, 1)은 1개의 원소 중에서 1개의 원소를 선택하는 경우의 수로서 1을 반환합니다.
따라서 combination(2, 1) = 1 + 1 = 2입니다.

combination(2, 2) = combination(1, 1)
combination(1, 1)은 1개의 원소 중에서 1개의 원소를 선택하는 경우의 수로서 1을 반환합니다.
따라서 combination(2, 2) = 1입니다.

그러면 combination(3, 2)를 계산합니다.
combination(3, 2) = combination(2, 1) + combination(2, 2)


이전에 계산한 결과를 대입하면 다음과 같습니다.
combination(3, 2) = 2 + 1 = 3


이제 마지막으로 combination(4, 3)를 계산합니다.
combination(4, 3) = combination(3, 2) + combination(3, 3)


이전에 계산한 결과를 대입하면 다음과 같습니다.
combination(4, 3) = 3 + 1 = 4

 


# 마지막으로 combination(5, 3)를 계산합니다.

 

combination(5, 3) = combination(4, 2) + combination(4, 3)
이전에 계산한 결과를 대입하면 다음과 같습니다.

combination(5, 3) = 6 + 4 = 10

 

반응형