입문 - 구슬을 나누는 경우의 수

입문 - 구슬을 나누는 경우의 수

문제설명

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

---

입출력 예

 

---

입출력 예 설명

입출력 예 #1

• 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.

입출력 예 #2

• 서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.

---

개선된 풀이

>> 처음에는 문제에 있는 힌트인 ' 서로 다른 n개 중 m개를 뽑는 경우의 수 공식'을 이용해서 풀려고 했으나, 오류가 발생. 아마도 공의 개수가 최대 30개인데, 30팩토리얼을 계산하면 숫자가 너무 커져서 int로는 불가능한 것 같다.

>> 이후에 구글링을 통해 풀 수 있는 여러가지 방법을 알게 되었다. 아래는 재귀함수를 이용한 방법이다.

>> share가 1인 경우에는 경우의 수가 balls의 수와 같고, balls의 수와 share의 수가 같으면 경우의 수가 1이다.

>> 아래는 chatgpt에서 가져온 반환값에 대한 설명이다.

1. solution(balls - 1, share - 1)은 현재 구슬의 개수 balls에서 하나를 빼고, 나눌 구슬의 개수 share에서 하나를 빼서 재귀적으로 호출됩니다. 이렇게 하면 한 개의 구슬을 나누는 경우를 계산합니다. 
2. solution(balls - 1, share)는 현재 구슬의 개수 balls에서 하나를 빼고, 나눌 구슬의 개수 share는 그대로 둔 채로 재귀적으로 호출됩니다. 

이 두 부분을 더하면, 현재 구슬을 선택하거나 선택하지 않고, 다음 구슬을 선택하는 경우의 수를 모두 합한 것이 됩니다. 이것이 모든 가능한 구슬 나누기의 경우의 수를 계산하는 핵심 아이디어입니다. 

>> 예를 들어 5개의 구슬 중 2개를 고른다면?

>> share가 1도 아니고, balls와 share 값도 다르기에 반환값에 들어가고, soultion(4,1) + solution(4,2)이 된다.

>> soultion(4,1)은 share가 1이기 때문에 4가 되고, solution(4,2)는 다시 재귀함수로 반환되서 soltuion(3,1) + soultion(3,2)가 된다.

>> solution(3,1)은 share가 1이기 때문에 3이 되고, solution(3,2)는 다시 재귀함수로 반환되서 soltuion(2,1) + solution(2,2)가 된다.

>> solution(2,1)은 share가 1이기 때문에 2가 되고, solution(2,2)는 값이 같기 때문에 1이 된다.

>> 모든 숫자를 더하면 경우의 수가 된다. 4 + 3 + 2 + 1 = 10

>> 재귀함수에 대한 내용은 2023년 10월 30일 TIL에 있다.

class Solution {
    public int solution(int balls, int share) {
        if (share == 1) {
            return balls;
        }
        if (balls == share) {
            return 1;
        }
        return solution(balls - 1, share - 1) + solution(balls - 1, share);
    }
}

 

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