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
